Home / Curated / Algorithms / Orthogonal matching pursuit

Orthogonal matching pursuit

Algorithms AIMech:OrthogonalMatchingPursuit DRAFT

Aliases: OMP

A greedy fixed-dictionary approximation algorithm that selects an atom correlated with the current residual and recomputes the approximation as the orthogonal projection of the signal onto the span of all selected atoms.

Identity Notes & Concept Scope The record selects finite real unit-norm dictionaries and exact maximum-correlation selection, while describing the original weak-selection formulation separately. Orthogonal refers to the residual and selected-span projection; the supplied dictionary need not be orthogonal. It is distinct from single-atom matching pursuit, a minimum-L1 principle, and a globally optimal subset search. OMP is a source-supported local alias; same-token environment RDF prefixes do not denote this AI concept. All 442 AIO IDs, labels and scoped synonyms and 525 preceding native IDs, names and aliases were compared. The only normalized hit was MP, an exact MarkovChain synonym; the full MarkovChain record and node distinguish that stochastic model from pursuit. Ignored/hidden-inclusive searches of both checkouts found the prior pursuit source lead, Markov-chain context, author initials and unrelated environment tokens or RDF prefixes, not an existing pursuit record. The semantic comparison read 107 AIO name/synonym/definition rows and 148 native name/definition rows; nine full AIO CLASS nodes and incident edges and twelve contextual YAMLs were inspected. Basis pursuit specifies exact minimum-L1 reconstruction, least-angle regression follows an equiangular path, and NMF fits nonnegative factors. This is a bounded identity assessment of the inspected corpus.

Claims & Grounded Evidence

6 Claims

Mechanism #select-and-refit

Starting from an empty selected set and residual y, choose an unselected unit atom maximizing absolute correlation with the current residual. Add it to the set, solve least squares over all selected columns and recompute the residual from that joint fit. In exact arithmetic the residual is orthogonal to the entire selected span. A nonzero correlated atom cannot already lie in that span. The method does not require the dictionary atoms to be mutually orthogonal.

supports Source: Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition · Locator: Sections 1–2.2, Equations 1–7 and algorithm Steps I–VII, PDF pp. 1–3 / printed pp. 40–42

Mechanism #recursive-projection-update

Let x_new=sum_i b_i*x_i+gamma, with gamma orthogonal to the old selected span. For a nonzero selected correlation, gamma is nonzero. In the real case the new coefficient is c=(r^T*x_new)/||gamma||^2, and each old coefficient changes from a_i to a_i-c*b_i. The squared residual decreases by abs(r^T*x_new)^2/||gamma||^2. The source’s recursive Gram-matrix implementation realizes this projection algebra; nearly dependent atoms can make finite-precision solves sensitive.

supports Source: Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition · Locator: Sections 2.1–2.3, Equations 4–12, PDF pp. 2–4 / printed pp. 41–43

Limitation #selected-subset-versus-global-optimum

Optimality of the least-squares fit is conditional on the selected subset; it is not optimal selection among all equally sized subsets. A curator example with unit columns [e1,e2,e3,b], b=(8/9,4/9,1/9), and y=e1-b selects e2 first, then e1 and e3 under lowest-index ties, requiring three atoms for zero residual. Yet e1-b is a two-atom representation, and no single atom is collinear with y. The documented fixed-cardinality and residual-tolerance objectives are approximation targets, not unconditional minimum-support guarantees.

supports Source: Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition · Locator: Section 2 opening paragraph and Section 2.2 remarks, PDF pp. 2–3 / printed pp. 41–42; curator-derived exact examples in research/discovery/pursuit-boundaries.py
supports Source: scikit-learn User Guide: Orthogonal Matching Pursuit · Locator: Section 1.1.9, approximate fixed-cardinality and residual-tolerance objectives

Limitation #finite-termination-conditions

With exact arithmetic, a finite dictionary and no premature tolerance stop, each nonzero-correlation selection adds an independent direction; the process reaches the projection onto the full dictionary span in at most its rank steps. This rank bound sharpens the paper’s dictionary-size bound by the stated independence argument. Residual zero additionally requires y to lie in that span. Early stopping, numerical rank decisions and noisy observations change the practical result and do not establish recovery of a generating support.

supports Source: Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition · Locator: Section 2.2, Theorem 2.1 and remarks, PDF p. 3 / printed p. 42; curator finite-dimensional independence consequence

Scope #weak-selection-and-printing-caveat

The original paper introduces a fixed-fraction correlation condition with 0<alpha<=1. Its page-3 algorithm box prints strict > against alpha times the supremum even though the earlier condition is >=; strict > is impossible at alpha=1. This record uses the consistent non-strict condition and exact finite maximum convention, also described in the versioned implementation guide, and preserves the apparent source inconsistency. The paper’s selected-correlation threshold delta>0 is an early-stop rule. Under weak selection, a selected correlation below delta need not mean that every available atom has correlation below delta.

supports Source: Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition · Locator: Section 1 correlation condition and Section 2.1 algorithm Steps II–III, PDF pp. 1,3 / printed pp. 40,42; curator-derived exact examples in research/discovery/pursuit-boundaries.py
supports Source: scikit-learn User Guide: Orthogonal Matching Pursuit · Locator: Section 1.1.9, maximum-correlation selection

Scope #runtime-and-method-boundaries

The paper contrasts whole-span refitting with MP and gives selected wavelet-decomposition examples. Fewer iterations do not imply universally lower cost: refitting adds work, and the conclusion’s speed expectation for highly redundant dictionaries is explicitly a conjecture. The exact selection score is absolute residual correlation with the original unit atom. The projection-energy decrease derived in the source is instead abs(r^T*x_new)^2/||gamma||^2; its atom-dependent denominator means the two scores need not select the same atom. This is an algebraic distinction within the inspected OMP formulation, not an attribution to an unaudited external algorithm. An external orthogonal-least-squares algorithm and its identity require separate primary-source assessment.

supports Source: Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition · Locator: Sections 2.1–4, Equation 7, Figures 1–5 and conclusion, PDF pp. 3–5 / printed pp. 42–44; curator-derived score-ranking example in research/discovery/pursuit-boundaries.py
supports Source: Matching Pursuits With Time-Frequency Dictionaries · Locator: Section III, Equations 11–17 and optional backprojection Equations 18–29, PDF pp. 3–5 / printed pp. 3399–3401; MP update contrasted with whole-span refitting

⚠️ Curated Limitations & Negative Results

The maintained definition is scoped to supplied finite real unit-norm dictionaries. Complex or infinite dictionaries, learned dictionaries, batch methods and recovery theorems need their own conditions and evidence.
Greedy representation is not a universal minimum-support or minimum-L1 solver. Ties, normalization, conditioning and stopping criteria can affect the selected representation.
Both original papers were visually read in full. No author implementation, model training or empirical benchmark was run; the rational examples are curator calculations. The record remains DRAFT and this work provides no independent scientific approval.
The apparent strict-inequality printing error is retained explicitly; no publisher erratum was located or claimed. Versioned scikit-learn documentation was read as corroboration, without claiming that every API option or numerical implementation was audited.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:SparseLearning` Sparse Learning	related_match	The pinned target is a representation-learning network that finds sparse linear representations and identifies their elements, with exact sparse-coding and dictionary-learning synonyms. Pursuit constructs a representation using a supplied fixed dictionary, so the sparse-representation connection is direct. It does not learn dictionary elements or require a neural network; related_match preserves those scope differences without a subclass or equivalence assertion. RepresentationLearning and SparseAutoEncoder are different neural scopes. LassoRegression, LinearRegression and LeastsquaresAnalysis do not specify this atom-selection procedure. FeatureExtraction can be an application, and MathematicalFunction is too generic to identify it. MarkovChain is unrelated despite its MP synonym.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`mallat1993`	Matching Pursuits With Time-Frequency Dictionaries Stéphane G. Mallat, Zhifeng Zhang	primary paper full_text	ID: https://doi.org/10.1109/78.258082 sha256:5f0efe79b524…
`pati1993`	Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition Y. C. Pati, R. Rezaiifar, P. S. Krishnaprasad	primary paper full_text	ID: https://doi.org/10.1109/ACSSC.1993.342465 sha256:8cb44738ff57…
`sklearn18`	scikit-learn User Guide: Orthogonal Matching Pursuit scikit-learn developers	official documentation documentation	sha256:358fa62c5481…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-12T12:17:49Z

Updated: 2026-10-12T12:26:58Z

Source File: data/curated/OrthogonalMatchingPursuit.yaml