Sparsity and incoherence in compressive sampling

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
\n
\nm\\geq \\mathrm{const}^{\\vphantom{\\frac12}}_{\\vphantom{\\frac12}} \\cdot\\mu^2(U)\\cdot S\\cdot\\log n,
\n
\nwhere 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,…

• NS
  National Science Foundation