Optimal sparse representations in general overcomplete bases

We consider the problem of enforcing a sparsity prior in underdetermined linear problems, which is also known as sparse signal representation in overcomplete bases. The problem is combinatorial in nature, and a direct approach is computationally intractable, even for moderate data sizes. A number of approximations have been considered in the literature, including stepwise regression, matching pursuit and its variants, and, recently, basis pursuit (ℓ₁) and also ℓ_p-norm relaxations with p<1. Although the exact notion of sparsity (expressed by an ℓ₀-norm) is replaced by ℓ₁ and ℓ_p norms in the latter two, it can be shown that under some conditions these relaxations solve the original problem exactly. The seminal paper of D.L. Donoho and X. Huo (see Stanford Univ. Tech. report: http://www-sccm.stanford.edu/pub/sccm/sccm02-17.pdf) establishes this fact for ℓ₁ (basis pursuit) for a special case where the linear operator is composed of an orthogonal pair. We extend their results to a general underdetermined linear operator. Furthermore, we derive conditions for the equivalence of ℓ₀ and ℓ_p problems, and extend the results to the problem of enforcing sparsity with respect to a transformation (which includes total variation priors as a special case). Finally, we describe an interesting result relating the sign patterns of solutions to the question of ℓ₁-ℓ₀ equivalence.