Sparse Signal Recovery via l1 Minimization

The purpose of this paper is to give a brief overview of the main results for sparse recovery via L optimization. Given a set of K linear measurements y=Ax where A is a Ktimes;N matrix, the recovery is performed by solving the convex program minparxpar₁ subject to Ax=y, where parxpar₁:=Sigma _t=0 ^N-1|x(t)|. If x is S-sparse (it contains only S nonzero components), and the matrix A obeys a certain type of uncertainty principle then the above equation will recover x exactly when K is on the order of S log N. The number of measurements it takes to acquire a sparse signal is within a constant log factor of its inherent complexity, even though we have no idea which components are important before hand. The recovery procedure can be made stable against measurement errors, and is computationally tractable.