Sparse representations: Recovery conditions and fast algorithm for a new criterion

Most applications of sparse representations are based on a combined ℓ₂-ℓ₁ criterion, where the least-squares-part ensures closeness to the observations and the ℓ₁-part sparsity. This choice leads to quite efficient algorithms and has a clear connection to maximum likelihood approaches in case of additive Gaussian noise. We replace the least-squares-part by a ℓ₁-part and investigate the recovery conditions of the so-obtained ℓ₁ - ℓ₁ criterion. We then propose an algorithm, that minimizes the criterion, in a finite number of steps.