A Caltech Library Service

Sparsity and incoherence in compressive sampling

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.

See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription
Candès, Emmanuel0000-0001-9234-924X
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
Record Number:CaltechAUTHORS:CANip07
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:8074
Deposited By: Archive Administrator
Deposited On:23 Jul 2007
Last Modified:08 Nov 2021 20:47

Repository Staff Only: item control page