Sparsity and Incoherence in Compressive Sampling

Emmanuel Candes; Justin Romberg

doi:10.1088/0266-5611/23/3/008

paper

Sparsity and Incoherence in Compressive Sampling

arXiv:math/0611957 · doi:10.1088/0266-5611/23/3/008

Abstract

We consider the problem of reconstructing a sparse signal $x^{0} \in R^{n}$ from a limited number of linear measurements. Given $m$ randomly selected samples of $U x^{0}$ , where $U$ is an orthonormal matrix, we show that $ℓ_{1}$ minimization recovers $x^{0}$ exactly when the number of measurements exceeds \[ m\geq \mathrm{Const}\cdotμ^2(U)\cdot S\cdot\log n, \] where $S$ is the number of nonzero components in $x^{0}$ , and $μ$ is the largest entry in $U$ properly normalized: $μ (U) = n \cdot max_{k, j} ∣ U_{k, j} ∣$ . The smaller $μ$ , the fewer samples needed. The result holds for ``most'' sparse signals $x^{0}$ supported on a fixed (but arbitrary) set $T$ . Given $T$ , if the sign of $x^{0}$ for each nonzero entry on $T$ and the observed values of $U x^{0}$ 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 this many samples.

Sparsity and Incoherence in Compressive Sampling

Abstract

References in corpus (2)

Cited by in corpus (217)