Sparse representations for image decompositions

We are given an image I and a library of templates L, such that L is an ove rcomplete 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 t he library templates. Each decomposition defines a representation for the i mage I, given L. What is an optimal representation for I given L and how to select it? We ar e 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 requi rements. 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 n orm, and the global minimum is obtained by searching through the local ones . Due to the computational complexity, i.e., the large number of local mini ma, we also study a greedy and iterative "weighted L-p Matching Pursuit" st rategy.