Chapter Summary

Chapter 13 Summary

Key Points

• 1.

  The sparse recovery problem is underdetermined but not hopeless. With $\mathbf{y} = \mathbf{A}\mathbf{x}+\mathbf{w}\in\mathbb{R}^M$, $\mathbf{A}\in\mathbb{R}^{M\times N}$, $M \ll N$, the linear system has infinitely many solutions. A sparsity prior ($\|\mathbf{x}\|_0 \leq s$) restores identifiability: when $s < \mathrm{spark}(\mathbf{A})/2$, the $s$-sparse solution is unique.

• 2.

  $\ell_0$ is NP-hard; $\ell_1$ is its convex hull. Natarajan (1995) proved the computational hardness of $\ell_0$-minimization. The $\ell_1$ relaxation replaces the combinatorial penalty by its tightest convex surrogate. Geometrically, the $\ell_1$ unit ball is a cross-polytope whose vertices coincide with $1$-sparse signals — minimizing $\|\mathbf{x}\|_1$ on an affine subspace is most likely to land on a vertex, hence on a sparse solution.

• 3.

  Basis Pursuit and LASSO are equivalent for suitable parameters. BPDN minimizes $\|\mathbf{x}\|_1$ s.t.\ $\|\mathbf{y}-\mathbf{A}\mathbf{x}\|_2\leq\epsilon$; LASSO minimizes $\tfrac{1}{2}\|\mathbf{y}-\mathbf{A}\mathbf{x}\|_2^2+\lambda\|\mathbf{x}\|_1$. They trace the same solution path as $\epsilon$ and $\lambda$ vary. Both are convex, hence solvable globally and efficiently by modern algorithms (Ch 14).

• 4.

  The RIP is the right stability condition. $\mathbf{A}$ satisfies RIP of order $s$ with constant $\delta_s$ when $(1-\delta_s)\|\mathbf{x}\|_2^2 \leq \|\mathbf{A}\mathbf{x}\|_2^2 \leq (1+\delta_s)\|\mathbf{x}\|_2^2$ for every $s$-sparse $\mathbf{x}$. If $\delta_{2s} < \sqrt{2}-1$, BPDN recovers every $s$-sparse $\mathbf{x}$ stably. Verifying RIP is NP-hard, but random Gaussian/Bernoulli matrices satisfy it with overwhelming probability when $M = O(s\log(N/s))$.

• 5.

  Coherence is a cheap surrogate for RIP. The mutual coherence $\mu(\mathbf{A})=\max_{i\neq j}|\langle\mathbf{A}_{i},\mathbf{A}_{j}\rangle|/(\|\mathbf{A}_{i}\|\|\mathbf{A}_{j}\|)$ can be computed in $O(MN^2)$. The Welch bound gives $\mu \geq \sqrt{(N-M)/(M(N-1))}$. Recovery holds when $s < \tfrac{1}{2}(1+1/\mu)$, a weaker but easier-to-check guarantee than RIP.

• 6.

  Recovery bounds degrade gracefully under noise. Noiseless RIP gives exact recovery; with noise $\|\mathbf{w}\|_2\leq\epsilon$, BPDN returns $\hat{\mathbf{x}}$ with $\|\hat{\mathbf{x}}-\mathbf{x}^\star\|_2 \leq C\epsilon + C'\sigma_s(\mathbf{x}^\star)_1/\sqrt{s}$. The first term is unavoidable noise propagation; the second penalises non-exact sparsity ($\sigma_s(\mathbf{x}^\star)_1 =$ best $s$-term approximation error). Oracle inequalities for LASSO show $\|\hat{\mathbf{x}}-\mathbf{x}^\star\|_2^2 = O(s\log N\cdot \sigma^2)$.