SCIENCE@home

Sparsity and incoherence in compressive sampling

E. Candès,J. Romberg

Published 2006 in Inverse Problems

ABSTRACT

We consider the problem of reconstructing a sparse signal from a limited number of linear measurements. Given m randomly selected samples of Ux0, where U is an orthonormal matrix, we show that ℓ1 minimization recovers x0 exactly when the number of measurements exceeds where S is the number of nonzero components in x0 and μ is the largest entry in U properly normalized: . 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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-31 of 31 references · Page 1 of 1

CITED BY

Showing 1-100 of 2178 citing papers · Page 1 of 22

123422
Next