Stable Signal Recovery from Incomplete and Inaccurate Measurements

Details Stable Signal Recovery from Incomplete and Inaccurate Measurements Stable Signal Recovery from Incomplete and Inaccurate Measurements

2005-03-03

arxiv.org/abs/math/0503066v2

Mathematics

Numerical Analysis

15 pages, 11 figures

Scientific paper

Suppose we wish to recover an n-dimensional real-valued vector x_0 (e.g. a digital signal or image) from incomplete and contaminated observations y = A x_0 + e; A is a n by m matrix with far fewer rows than columns (n << m) and e is an error term. Is it possible to recover x_0 accurately based on the data y? To recover x_0, we consider the solution x* to the l1-regularization problem min \|x\|_1 subject to \|Ax-y\|_2 <= epsilon, where epsilon is the size of the error term e. We show that if A obeys a uniform uncertainty principle (with unit-normed columns) and if the vector x_0 is sufficiently sparse, then the solution is within the noise level \|x* - x_0\|_2 \le C epsilon. As a first example, suppose that A is a Gaussian random matrix, then stable recovery occurs for almost all such A's provided that the number of nonzeros of x_0 is of about the same order as the number of observations. Second, suppose one observes few Fourier samples of x_0, then stable recovery occurs for almost any set of p coefficients provided that the number of nonzeros is of the order of n/[\log m]^6. In the case where the error term vanishes, the recovery is of course exact, and this work actually provides novel insights on the exact recovery phenomenon discussed in earlier papers. The methodology also explains why one can also very nearly recover approximately sparse signals.

Affiliated with

Also associated with

No associations

Rating

Stable Signal Recovery from Incomplete and Inaccurate Measurements does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Stable Signal Recovery from Incomplete and Inaccurate Measurements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stable Signal Recovery from Incomplete and Inaccurate Measurements will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-24292