Chapter 13: Sparsity and the $\ell_1$ Relaxation

Learning Objectives

• Formulate the sparse recovery problem $\mathbf{y} = \mathbf{A}\mathbf{x} + \mathbf{w}$ and explain why $\ell_0$ minimization is NP-hard
• State and interpret the Basis Pursuit and LASSO programs as convex relaxations of $\ell_0$
• Explain geometrically why the $\ell_1$ ball promotes sparsity via its polytope vertices
• State the Restricted Isometry Property (RIP) and the $\delta_{2s} < \sqrt{2} - 1$ sufficient condition
• Derive the sample complexity $M = O(s \log(N/s))$ for Gaussian sensing matrices
• Bound mutual coherence by the Welch bound and relate coherence to RIP
• State exact recovery guarantees in the noiseless regime and stable recovery under bounded noise
• Interpret the LASSO oracle inequality and the role of the regularization parameter $\lambda$