A set of algorithmic procedures for estimating a sparse or compressible signal x from underdetermined and/or noisy linear measurements y = Φx + n by imposing or promoting sparsity—using methods such as ℓ1‑regularized convex optimization, greedy pursuit algorithms (OMP, CoSaMP), iterative thresholding, or Bayesian sparse priors. Sparse recovery focuses on the solver and algorithmic trade‑offs (accuracy, complexity, robustness) given a measurement model and a sparsifying dictionary or basis.

Principle

Enforcement of a sparsity prior biases the inverse problem toward solutions with few nonzero components; under conditions on Φ and the dictionary (e.g., low mutual coherence, RIP) convex relaxations and greedy algorithms can recover the true sparse support or approximate it with bounded error in the presence of noise.

Demonstration

Illustrative scenario → measurements y obtained from y=Φx with Φ known and x s‑sparse. Recognition → initial residual computed. Action → apply orthogonal matching pursuit: iteratively select the dictionary atom most correlated with the residual, update residual and coefficients until stopping criterion. Consequence → when coherence and SNR permit, OMP recovers support and coefficients in O(s·m·N) operations; otherwise it may miss components or select false atoms. (Constructed algorithmic example.)

Misapplication

Interpreting sparsity‑promoting estimates as proof of true sparsity without accounting for model mismatch or noise: regularizers can produce sparse solutions even when the underlying signal is not sparse, leading to false discovery. Another error is ignoring dictionary coherence: recovery guarantees depend critically on measurement/dictionary properties.

Consequence

Enables reconstruction from fewer measurements than unconstrained methods, with practical outcomes determined by algorithm choice: some methods favor speed (greedy), others stability (convex solvers), and all face failure modes—support misidentification, bias in amplitude estimates, and sensitivity to noise and coherence.

Reversal

If the dictionary is highly coherent or the signal is not sparse/compressible in the assumed basis, sparse recovery algorithms can fail systematically—requiring alternative priors, improved measurement design, or models that accept denser representations. In regimes of extreme noise, sparsity promotion can amplify estimation bias.

Boundary

Clearly within → linear measurement model y=Φx with known Φ, x exactly s‑sparse in the chosen dictionary, and Φ satisfying coherence/RIP conditions. Boundary case → compressible x or partially unknown dictionary (dictionary learning required). Clearly outside → nonlinear measurement models or dense signals without parsimonious representation where least‑squares or other dense inference is appropriate.

Semantic Tension

Parsimony (sparse explanations) versus fidelity to data—stronger sparsity priors reduce variance and can improve interpretability but risk bias and false negatives when the model is mismatched.

Synthesis

Sparse signal recovery operationalizes parsimony as an inferential regularizer: algorithm selection and measurement/dictionary design jointly determine whether sparsity is a valid structural prior or a misleading artifact of regularization.