and segmentation, image compression, object identification or recognition, and others. The complexity of the signal comes from the dimension of the images and by the large number of variations that can occur, such as contrast, luminance, occlusions, perspective, scale, rotation, etc.. This variety of problems has been tackled

with different methods, with many of them depending on a transformation of the signal into a more meaningful representation. For instance, image compression

relies on the fact that images can be accurately represented by a small number of elements of a proper basis. These include the Fourier or wavelet domains, but in fact

any collection of elements can be used to efficiently represent images, as long as they constitute sources commonly found in images. This suggests that images belong to a type of signal that can be targeted by the sparse coding framework.

Sparse coding assumes that a certain class of signals can be expressed linearly by a small number of elements from a given set or frame. A range of image processing

problems can then be solved by cleverly formulating an optimization problem with three main components: an objective function that matches the criterion to optimize,

an appropriate frame or dictionary, and a penalty or constraint that enforces sparsity of the image representation. Strictly speaking, the sparsity of a vector is defined by