Sparse representations for image decompositions

We are given an image I and a library of templates L, such that L is an overcomplete basis for I. The templates can represent objects, faces, features, analytical functions, or be single pixel templates (canonical templates). There are infinitely many ways to decompose I as a linear combination of the library templates. Each decomposition defines a representation for the image I, given L. What is an optimal representation for I given L and how to select it? We are motivated to select a sparse/compact representation for I, and to account for occlusions and noise in the image. We present a concave cost function criterion on the linear decomposition coefficients that satisfies our requirements. More specifically, we study a "weighted L-p norm" with 0 < p < 1. We prove a result that allows us to generate all local minima for the L-p norm, and the global minimum is obtained by searching through the local ones. Due to the computational complexity, i.e., the large number of local minima, we also study a greedy and iterative "weighted L-p Matching Pursuit" strategy.