Sparsity and Incoherence in Compressive Sampling

Details Sparsity and Incoherence in Compressive Sampling Sparsity and Incoherence in Compressive Sampling

2006-11-30

arxiv.org/abs/math/0611957v1

Mathematics

Statistics Theory

Scientific paper

10.1088/0266-5611/23/3/008

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 $\ell_1$ minimization recovers $x^0$ exactly when the number of measurements exceeds \[ m\geq \mathrm{Const}\cdot\mu^2(U)\cdot S\cdot\log n, \] where $S$ is the number of nonzero components in $x^0$, and $\mu$ is the largest entry in $U$ properly normalized: $\mu(U) = \sqrt{n} \cdot \max_{k,j} |U_{k,j}|$. The smaller $\mu$, 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 $Ux^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.

Affiliated with

Also associated with

No associations

Rating

Sparsity and Incoherence in Compressive Sampling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sparsity and Incoherence in Compressive Sampling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sparsity and Incoherence in Compressive Sampling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-423122