OMP

From SparseSolver

Solver Name OMP Authors N/A Initial release date N/A Latest release date N/A Solver type Greedy Programming Language N/A License N/A Webpage [N/A link]

Orthogonal matching pursuits is one of the most basic greedy algorithms. It is widely used because it is simple to implement and analyze, and there have been many variations to it, such as StOMP, ROMP, and CoSaMP. The method comes from an improvement over simple "matching pursuits"^[1] which has been used since the 1980s or earlier.

In statistics, this may be known as forward stepwise regression.

Contents 1 Basic Idea 2 Analysis 3 Implementations 4 See Also 5 References

Basic Idea

Since it is a greedy algorithm, the method seeks to update the estimate of the signal without taking into account global structure. At every step, the optimal choice is performed. OMP adds exactly one atom to the signal at every iteration.

If b are the observations and A is the measurement matrix (the matrix of atoms), start with x = 0 and the residual r(x) = Ax − b. Every step consists of two parts.

1. First, select the atom i that is most correlated with the residual r(x).
2. Second, update x by solving the least-squares problem using only the atoms that have been previously selected.

Analysis

OMP has recovery guarantees almost as good as l1 recovery^[2][3] for the case of Gaussian matrices, and was one of the first methods to be nicely analyzed ^[4]. Further analysis (using RIP) in 2011 is in ^[5]. A Brownian Motion analysis is in ^[6].

Implementations

Quite easy to implement yourself in a high-level language like Matlab. The main issue is solving a least-squares problem. For largescale problems, this can be done with an iterative method (CG, MINRES). The cost of the algorithm grows cubically in the number of nonzero entries of the solution, so it is best for very sparse solutions.

• SPAMS. This is a serious toolbox and has C++/mex files, with Matlab, and uses LAPACK and BLAS (via ATLAS or Intel MKL if available). In July 2011, they made it open-source. Some of the algorithms are theirs, but they also implement existing algorithms when appropriate (or add their own tweaks).
• SparseLab at Stanford includes an implementation of OMP, among many other algorithms. Their package is in Matlab.
• Matlab implementation at Mathworks, written by Stephen.
• Some OMP and KSVD implementations at Ron Rubinstein's page

See Also

• StOMP (Stagewise OMP)
• ROMP (Robust OMP)
• CoSaMP (Compressive Sampling Matching Pursuit)
• Look ahead OMP ^[7]
• A* Orthogonal Matching Pursuit (A*OMP) algorithm (AStarOMP software) by Karahanoglu and Erdogan, a general sparse recovery algorithm employing A* search on a hypothesis tree where the paths are extended and evaluated in a way similar to OMP. arXiv:1009.0396
• OMPR. Orthogonal Matching Pursuit with Replacement by Prateek Jain Ambuj Tewari Inderjit S. Dhillon, NIPS 2011. Like OMP, it adds one coordinate per step; the novelty is that it removes one coordinate per step too, and this gives OMPR much stronger guarantees than OMP under a RIP assumption. They also have OMPR-Hash, which they say is the first sub-linear sparse recovery algorithm.

References

1. ↑ S. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Trans. Sig. Proc. 41 (1993), 3397--3415.
2. ↑ J. A. Tropp and A. C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Tran. Info. Theory 53 (2007), no. 12.
3. ↑ M. A. Davenport and M. B. Wakin, Analysis of orthogonal matching pursuit using the restricted isometry property, IEEE Trans. Info. Theory 56 (2010), no. 9, 4395--4401.
4. ↑ J. A. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Inform. Theory 50 (2004), 2231--2242.
5. ↑ "Improved RIP Analysis of Orthogonal Matching Pursuit" by Ray Maleh, arXiv:1102.4311
6. ↑ Orthogonal Matching Pursuit: A Brownian Motion Analysis by Alyson K. Fletcher and Sundeep Rangan, arXiv:1105.5853
7. ↑ Look ahead orthogonal matching pursuit, S. Chatterjee, D. Sundman, and M. Skoglund, ICASSP 2011. link