Sparse Signal Recovery via l_1 Minimization

Abstract

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_1 subject to Ax=y, where parxpar_1:=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.

Additional details