Candès, Emmanuel and Romberg, Justin (2007) Sparsity and incoherence in compressive sampling. Inverse Problems, 23 (3). pp. 969-985. ISSN 0266-5611. doi:10.1088/0266-5611/23/3/008. https://resolver.caltech.edu/CaltechAUTHORS:CANip07
![]()
|
PDF
See Usage Policy. 420kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:CANip07
Abstract
We consider the problem of reconstructing a sparse signal x^0\in{\bb R}^n from a limited number of linear measurements. Given m randomly selected samples of Ux0, where U is an orthonormal matrix, we show that ell1 minimization recovers x0 exactly when the number of measurements exceeds m\geq \mathrm{const}^{\vphantom{\frac12}}_{\vphantom{\frac12}} \cdot\mu^2(U)\cdot S\cdot\log n, where S is the number of nonzero components in x0 and μ is the largest entry in U properly normalized: \mu(U) = \sqrt{n} \cdot \max_{k,j} |U_{k,j}| . The smaller μ is, the fewer samples needed. The result holds for 'most' sparse signals x0 supported on a fixed (but arbitrary) set T. Given T, if the sign of x0 for each nonzero entry on T and the observed values of Ux0 are drawn at random, the signal is recovered with overwhelming probability. Moreover, there is a sense in which this is nearly optimal since any method succeeding with the same probability would require just about as many samples.
Item Type: | Article | ||||||
---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||
ORCID: |
| ||||||
Additional Information: | Copyright © Institute of Physics and IOP Publishing Limited 2007. Received 17 December 2006; Published 10 April 2007; Print publication: Issue 3 (June 2007) EC is partially supported by National Science Foundation grants ITR ACI-0204932 and CCF515362, by the 2006 Waterman Award (NSF), and by a grant from DARPA. JR is supported by National Science Foundation grants CCF515362 and ITR ACI-0204932. EC would like to thank Joel Tropp and Houman Owhadi for fruitful conversations related to this project. | ||||||
Issue or Number: | 3 | ||||||
DOI: | 10.1088/0266-5611/23/3/008 | ||||||
Record Number: | CaltechAUTHORS:CANip07 | ||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:CANip07 | ||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
ID Code: | 8074 | ||||||
Collection: | CaltechAUTHORS | ||||||
Deposited By: | Archive Administrator | ||||||
Deposited On: | 23 Jul 2007 | ||||||
Last Modified: | 08 Nov 2021 20:47 |
Repository Staff Only: item control page