Candes, Emmanuel and Romberg, Justin and Tao, Terence (2006) Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics, 59 (8). pp. 12071223. ISSN 00103640. doi:10.1002/cpa.20124. https://resolver.caltech.edu/CaltechAUTHORS:20110224142938349

PDF
 Accepted Version
See Usage Policy. 482kB 
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20110224142938349
Abstract
Suppose we wish to recover a vector x_0 Є R^m (e.g., a digital signal or image) from incomplete and contaminated observations y = Ax_0 + e; A is an 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 ℓ_(1)regularization problem min ‖x‖ℓ_1 subject to ‖Ax  y‖ℓ(2) ≤ Є, where Є is the size of the error term e. We show that if A obeys a uniform uncertainty principle (with unitnormed columns) and if the vector x_0 is sufficiently sparse, then the solution is within the noise level ‖x^#  x_0‖ℓ_2 ≤ C Є. 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. As a second instance, suppose one observes few Fourier samples of x_0; then stable recovery occurs for almost any set of n 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 into the exact recovery phenomenon discussed in earlier papers. The methodology also explains why one can also very nearly recover approximately sparse signals.
Item Type:  Article  

Related URLs: 
 
ORCID: 
 
Additional Information:  © 2006 Wiley Periodicals, Inc. Received February, 2005; Revised June, 2005. Article first published online: 1 Mar 2006. E. C. is partially supported by a National Science Foundation grant DMS 0140698 (FRG) and by an Alfred P. Sloan Fellowship. J. R. is supported by National Science Foundation grants DMS 0140698 and ITR ACI0204932. T. T. is supported in part by grants from the Packard Foundation.  
Funders: 
 
Subject Keywords:  ℓ1minimization, basis pursuit, restricted orthonormality, sparsity, singular values of random matrices.  
Issue or Number:  8  
DOI:  10.1002/cpa.20124  
Record Number:  CaltechAUTHORS:20110224142938349  
Persistent URL:  https://resolver.caltech.edu/CaltechAUTHORS:20110224142938349  
Official Citation:  Stable signal recovery from incomplete and inaccurate measurements (pages 1207–1223) Emmanuel J. Candès, Justin K. Romberg and Terence Tao DOI: 10.1002/cpa.20124  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  22496  
Collection:  CaltechAUTHORS  
Deposited By:  INVALID USER  
Deposited On:  24 Feb 2011 23:41  
Last Modified:  09 Nov 2021 16:05 
Repository Staff Only: item control page