Summary: Suppose we wish to recover a vector (e.g., a digital signal or image) from incomplete and contaminated observations ; is an matrix with far fewer rows than columns and is an error term. Is it possible to recover accurately based on the data y?
To recover , we consider the solution to the 1-regularization problem
where is the size of the error term . We show that if obeys a uniform uncertainty principle (with unit-normed columns) and if the vector is sufficiently sparse, then the solution is within the noise level
As a first example, suppose that is a Gaussian random matrix; then stable recovery occurs for almost all such ’s provided that the number of nonzeros of is of about the same order as the number of observations. As a second instance, suppose one observes few Fourier samples of ; then stable recovery occurs for almost any set of coefficients provided that the number of nonzeros is of the order of . In the case where the error term vanishes, the recovery is of course exact, and this work actually provides novel insights into the exact recovery phenomenon discussed in earlier papers. The methodology also explains why one can also very nearly recover approximately sparse signals.