Fast implementation of a ℓ1 - ℓ1 regularized sparse representations algorithm.

When seeking a sparse representation of a signal on a redundant basis, one replaces generally the quest for the true sparsest model by an lscr₁ minimization and solves thus a linear program. In the presence of noise one further replaces the exact reconstruction constraint by an approximate one. The lscr₂-norm is generally chosen to measure the reconstruction error because of its link with Gaussian noise and the stability and simplicity of the ensuing algorithms, but the lscr₁-norm may be preferred in some cases when the noise has heavier tails or in the presence of outliers. We propose to replace the usual lscr₂ - lscr₁ regularized criterion by a lscr₁ - lscr₁ regularized criterion and show how to construct a fast dedicated optimization algorithm that solves this criterion in a finite number of steps. Since quite often even these fast optimal programs are considered to be too time consuming, we further develop an ad hoc sub-optimal algorithm that could be called the lscr₁-matching pursuit algorithm.