TL;DR
This paper introduces Orthogonal Matching Pursuit (OMP), a refined greedy algorithm for approximating functions using overcomplete dictionaries. By ensuring the approximation error is orthogonal to all previously selected basis functions at every step, OMP achieves faster convergence and superior finite-step performance compared to the original Matching Pursuit (MP) algorithm.
What Problem Does This Paper Address?
In signal processing and functional approximation, we often want to represent a complex signal as a sum of simpler "building blocks" called atoms, which together form a dictionary. When this dictionary is "overcomplete" (meaning there are more atoms than dimensions in the space), finding the best sparse representation is computationally hard.
The standard approach at the time was Matching Pursuit (MP), a greedy algorithm that picks the atom most correlated with the current residual (error) and subtracts its projection. However, MP has a major flaw: it only ensures the new residual is orthogonal to the last atom picked. It might "re-pick" directions it already covered, leading to slow, suboptimal convergence in finite iterations. As shown in Figure 1, even in a simple 2D case, MP can take many steps to converge if the dictionary atoms are not orthogonal.
Methods
The authors propose Orthogonal Matching Pursuit (OMP). The core innovation is a "full backward orthogonality" requirement. At each iteration $k$:
- Selection: Like MP, OMP finds the atom in the dictionary that has the highest inner product with the current residual.
- Orthogonalization: Unlike MP, OMP re-calculates the coefficients for all atoms selected so far to ensure the new residual is orthogonal to the entire subspace spanned by those atoms.
- Recursion: To prevent the computational cost from exploding, the authors derive a recursive update formula. They use an auxiliary model to describe how the new atom relates to previous ones, allowing them to update the approximation coefficients efficiently without re-solving the entire projection from scratch at every step.
Datasets
The paper evaluates the algorithm using synthetic numerical examples rather than large-scale public datasets. Specifically, they use:
- Wavelet Dictionaries: An affine wavelet frame constructed from dilates and translates of the second derivative of a Gaussian (351 total vectors).
- Example I: A complex signal (shown in Figure 2a) decomposed using the wavelet dictionary.
- Example II: A signal specifically constructed to lie within the span of exactly three dictionary atoms.
Key Insights and Ideas
- Finite Convergence Guarantee: For a dictionary of size $N$, OMP is guaranteed to converge to the optimal projection in at most $N$ steps. MP, by contrast, only guarantees asymptotic convergence.
- The "Energy Conservation" Equation: The authors show that the squared norm of the residual decreases by a specific amount related to the projection onto the newly selected (and orthogonalized) component. This provides a rigorous basis for its improved convergence.
- Computational Trade-off: OMP is more "expensive" per iteration than MP because of the orthogonalization step. However, because it requires significantly fewer iterations to reach a target error, it can be more efficient overall, especially for highly redundant dictionaries.
Key Results
The quantitative improvements are striking. In Example I, OMP converges in far fewer iterations than MP to reach the same error level (see Figure 2b).
In Example II, where the signal is composed of three specific atoms, OMP converges exactly in three iterations. The authors note that for this specific signal, MP is approximately 20 times more computationally expensive than OMP to reach the same accuracy, despite OMP's higher cost per step.
Limitations and Future Work
- Computational Overhead: While recursive, the orthogonalization step still involves solving a system of linear equations (or updating a matrix inversion) at each step. For extremely large dictionaries or very high-dimensional signals, this overhead might become a bottleneck.
- Dictionary Sensitivity: The authors acknowledge that the relative performance of OMP vs. MP depends heavily on the specific signal and the redundancy of the dictionary.
- Future Directions: The paper suggests that OMP is particularly well-suited for "very redundant" dictionaries where it can exploit the redundancy to reduce error as quickly as possible. Further research into even more efficient recursive implementations for specific dictionary structures (like wavelets) is implied.
Summary updated