Can the same atom be selected again?

Yes. With nonorthogonal atoms, later updates can make an earlier atom correlate with the residual again.

Does the dictionary have to be a basis?

No. Redundant dictionaries are a central motivation for the method.

Does each step reduce error?

An exact projection onto a normalized selected atom cannot increase squared residual norm. Approximate numerical implementations should still be checked.

AI Glossary / Statistics and probability / Advanced

Matching pursuit

Definition

Matching pursuit is a greedy algorithm that approximates a signal or vector by repeatedly selecting a dictionary element that closely matches the current residual and subtracting its contribution. The dictionary elements, often called atoms, are usually normalized and may be redundant rather than forming an orthogonal basis. The method builds an adaptive representation one component at a time. A short representation can be useful, but ordinary matching pursuit does not generally guarantee the sparsest possible solution.

What it means

The residual is the portion not yet explained by the selected components. At each step, the algorithm asks which available atom best aligns with that residual. This differs from choosing all components in advance or solving a global optimization problem over every possible subset.

A dictionary can contain more atoms than the vector's dimension, allowing several possible descriptions of the same signal. That flexibility can capture patterns efficiently, but similar atoms can compete with one another. The chosen representation depends on the dictionary, selection rule, tie handling, and stopping criterion.

How it works

Start with residual r0 equal to the input vector. For a finite dictionary of unit-norm real atoms g_j, select an atom maximizing the absolute inner product |rᵀg_j|. Set its coefficient to rᵀg_j and subtract that coefficient times the atom from the residual. Add the selected contribution to the running approximation.

Repeat until a residual tolerance, iteration limit, or other justified stopping rule is reached. Each exact projection step reduces squared residual norm by the square of the selected coefficient. The new residual is orthogonal to the atom just selected, but generally not to all previously selected atoms.

Ordinary matching pursuit updates through successive one-atom projections. Orthogonal matching pursuit instead refits coefficients jointly over the selected atoms at each iteration. This distinction affects residuals, computational cost, and the possibility of revisiting atoms; the two algorithms should not be treated as interchangeable implementations.

Three practical examples

A signal-processing project represents a recording using a small collection of time-localized oscillatory atoms.
An image-processing study approximates patches using a redundant dictionary and evaluates the quality of the resulting sparse descriptions.
An AI research exercise uses matching pursuit to illustrate greedy feature selection and the consequences of correlated dictionary elements.

Think of it this way

Think of describing a complex sound by repeatedly removing the strongest recognizable instrument-like component. After each removal, listen to what remains and choose the next component. Because the available sound patterns overlap, removing one component can change how earlier patterns fit. The analogy explains the iterative residual process without promising that the selected sounds reveal the true physical sources.

Worked example

Consider an original real-vector example with x = (2,1). Use unit atoms g1 = (1,0), g2 = (0,1), and g3 = (1,1)/sqrt(2). The initial inner products are 2, 1, and 3/sqrt(2), approximately 2.121, so select g3.

Its coefficient is 3/sqrt(2), giving a contribution (1.5,1.5). The residual becomes (0.5,−0.5). Squared residual norm falls from 5 to 0.5, a reduction of 4.5, which equals the squared coefficient.

The next absolute inner products with g1 and g2 are tied at 0.5; choose g1 by a declared tie rule. Subtracting 0.5g1 leaves residual (0,−0.5), whose squared norm is 0.25. This new residual has inner product −0.5/sqrt(2) with g3, so it is no longer orthogonal to that earlier atom.

If orthogonal matching pursuit refitted the selected atoms g3 and g1, it could represent x exactly as sqrt(2)g3 + g1. Ordinary matching pursuit's two-step approximation has not done that joint refit. The example verifies both the energy reduction and the difference between the algorithms.

Illustrative case study

Fictional case: SignalWillow experiments with compact representations of machine recordings. It chooses a dictionary containing short pulses and oscillatory patterns, then records how residual energy decreases as matching pursuit selects atoms.

The team notices that some highly similar atoms are selected repeatedly and that very long runs begin fitting background noise. It evaluates stopping rules on separate recordings and compares the method with alternatives, including a joint-refitting variant. Engineers interpret the selected atoms as descriptive features until additional evidence connects them to actual machine behavior. The case separates useful approximation from unsupported claims about physical causes.

Common misconceptions and mistakes

Greedy selection does not guarantee the globally smallest residual for a fixed number of atoms or the sparsest exact representation. A normalized dictionary matters: comparing raw inner products across unequal atom norms can favor scale rather than alignment.

The residual need not remain orthogonal to every previously selected atom. Ordinary matching pursuit is therefore not simply another name for orthogonal matching pursuit. A good reconstruction also does not prove that selected atoms are the real generating components. Finally, driving residual error toward zero can fit noise or irrelevant detail when the application calls for compression or generalization.

Business use

Businesses working with signals, images, or structured numerical features may use matching pursuit as part of a representation pipeline. Its appeal is the understandable sequence of chosen components and the ability to stop at a desired approximation budget.

Evaluate dictionary quality, reconstruction error, runtime, stability, and downstream usefulness. Keep training and evaluation data separate when the dictionary is learned from examples. Document normalization, search approximations, tie rules, and stopping criteria so results can be reproduced. A compact representation should be judged against the actual task, such as storage or prediction, rather than the number of selected atoms alone.

Check your understanding

After two ordinary matching-pursuit steps, must the residual be orthogonal to both selected atoms?

Answer: No. It is orthogonal to the latest atom immediately after that projection. A later nonorthogonal update can reintroduce correlation with an earlier atom, as the worked example demonstrates.

Related terms

Residual
Greedy algorithms
Inner product
Orthogonal Matching Pursuit
dictionary atom
sparse approximation
greedy algorithm
overcomplete dictionary
signal representation

Learn next

Review vector projections and normalized inner products, then compare matching pursuit with orthogonal matching pursuit and optimization-based sparse coding. Explore how dictionary coherence affects selection and approximation stability.

Orthogonal Matching Pursuit

Sources

Mallat and Zhang, "Matching Pursuits With Time-Frequency Dictionaries," original paper, especially section III: https://www.di.ens.fr/~mallat/papiers/MallatPursuit93.pdf

The scanned mathematical definition was visually checked. The two-dimensional example is original and independently computed, including the joint-refitting comparison. SignalWillow is fictional.

Previous: Matching network Next: Materialized view