Chapter 14: Algorithms for Sparse Recovery

Learning Objectives

• Derive ISTA from the proximal gradient perspective and prove its $O(1/k)$ convergence
• Understand FISTA's Nesterov momentum acceleration and its $O(1/k^2)$ rate
• Formulate the LASSO via variable splitting and execute the ADMM updates
• Implement greedy algorithms (OMP, CoSaMP, IHT) and reason about when they outperform convex relaxations
• Connect Bayesian sparse models (spike-and-slab, Bernoulli-Gaussian, SBL) to $\ell_0$ / $\ell_1$ regularization