What Are Pursuit Algorithms?

Pursuit algorithms are iterative computational methods designed to find sparse representations of signals or data by selecting basis elements from an overcomplete dictionary that best approximate a target signal. The central problem these algorithms address arises in compressed sensing and sparse signal recovery: given a set of underdetermined linear measurements, identify the sparse combination of dictionary atoms that most closely reconstructs the original signal. Pursuit algorithms draw on ideas from optimization, linear algebra, and approximation theory, and have become foundational tools in signal processing, statistics, and machine learning.

The term "pursuit" reflects the iterative nature of these methods: each step pursues a better approximation by selecting or updating the active set of dictionary elements. The family includes both greedy approaches, which make locally optimal decisions at each step, and convex relaxation approaches, which reformulate the combinatorial sparse recovery problem as a tractable optimization.

Greedy Pursuit Methods

Matching Pursuit (MP), introduced by Mallat and Zhang in 1993, is the earliest and most structurally simple greedy pursuit algorithm. At each iteration, MP selects the dictionary atom most correlated with the current residual and adds a scaled version of it to the running approximation, then subtracts that contribution and repeats. The residual does not converge to zero in a minimum number of steps because the selected atoms are not made orthogonal to each other. Orthogonal Matching Pursuit (OMP) corrects this by projecting the current approximation onto the span of all selected atoms at each step, guaranteeing that the residual is orthogonal to all previously selected atoms. As established in published work on OMP for sparse signal recovery with noise in IEEE Transactions on Information Theory, OMP can reliably recover a signal with m nonzero components from O(m log d) random linear measurements in dimension d. Variants such as Stagewise OMP, Compressive Sampling Matching Pursuit (CoSaMP), and Subspace Pursuit extend the basic algorithm with batch selection and pruning strategies for improved efficiency on large problems.

Basis Pursuit and Convex Relaxation

Basis Pursuit (BP) reformulates sparse recovery as a convex optimization problem: minimize the L1 norm of the coefficient vector subject to the constraint that the dictionary-weighted combination matches the measurements. Because the L1 norm is the convex envelope of the L0 sparsity count, minimizing it tends to produce sparse solutions without the combinatorial search that exact L0 minimization would require. The connection between the L1 formulation and compressed sensing recovery guarantees is made precise through the restricted isometry property (RIP) of the measurement matrix. Research from Caltech on signal recovery from random measurements via OMP by Tropp and Gilbert provides theoretical bounds showing OMP and BP require comparable numbers of measurements to achieve reliable recovery. In practice, BP solved via second-order cone programming or the LASSO formulation handles noisy measurements by allowing a small constraint violation, producing the Basis Pursuit Denoising problem widely used in practice.

Adaptive and Structured Variants

Adaptive pursuit algorithms, including Adaptive Matching Pursuit and Regularized OMP, allow both addition and removal of atoms from the active set across iterations, correcting mistakes made in early greedy steps. Dictionary learning extends the pursuit framework to the regime where the dictionary itself is unknown and must be estimated from training data. The SIAM Journal on Imaging Sciences has published work on randomized OMP variants with partial selection strategies that reduce per-iteration cost while maintaining recovery guarantees, making these methods practical for large-scale imaging and hyperspectral data.

Applications

Pursuit algorithms have applications in a wide range of fields, including:

• Compressed sensing for magnetic resonance imaging and radar
• Audio and image compression beyond traditional transform coding
• Channel estimation and equalization in wireless communications
• Feature selection and sparse regression in machine learning
• Hyperspectral image unmixing in remote sensing