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.