A greedy iterative algorithm for sparse approximation that builds a k-sparse representation of a signal by repeatedly selecting the dictionary atom most correlated with the current residual, orthogonally projecting the signal onto the span of selected atoms to update coefficients, and updating the residual until a stopping criterion is met.

Principle

At each iteration, choose the dictionary element with maximal absolute inner product with the residual (greedy selection), then recompute coefficients by solving a least-squares problem on the selected atoms (orthogonal projection) to ensure previously selected atoms are not re-weighted inconsistently, reducing residual norm monotonically.

Demonstration

Approximating a signal y with a redundant basis (dictionary): initialize residual r=y, select the atom with largest correlation , add it to the active set, solve the least-squares problem to compute coefficients on the active set, update r=y - D_active c_active, and repeat until residual norm or sparsity target is reached, producing an interpretable sparse code.

Misapplication

Stopping OMP too early when essential atoms remain unselected, producing biased approximations, or applying OMP when the dictionary columns are highly coherent without modifications (e.g., regularization), which can cause incorrect atom selection and poor recovery.

Consequence

When conditions like sparsity level and incoherence/Restricted Isometry conditions roughly hold, OMP recovers sparse representations quickly with interpretable support sets and low computational cost compared with exhaustive search; it provides a clear trade-off between sparsity and approximation error.

Reversal

Dense least-squares fit on the full dictionary: solve a global L2 minimization using all atoms, yielding lower residual for a given norm but producing dense coefficients without enforced sparsity or interpretability of selected atoms.

Boundary

Scope: linear sparse approximation problems with an explicit dictionary matrix and moderate coherence where greedy selection is meaningful; excludes problems requiring exact l0 minimization in very coherent dictionaries, or signals better modeled by structured (grouped or hierarchical) sparsity without adaptation of the algorithm.

Semantic Tension

Tension between greediness and global optimality: OMP's local, greedy choices are fast and interpretable but can miss globally optimal sparse supports; this contrasts with convex-relaxation approaches (L1 minimization) that offer different trade-offs between robustness and computational cost.

Synthesis

Orthogonal Matching Pursuit is a greedy sparse-coding algorithm that iteratively selects the dictionary atom most correlated with the current residual and recomputes coefficients by orthogonal projection to build a sparse representation with monotone residual reduction and interpretable support.