Orthogonal Matching Pursuit

A Greedy Algorithm that aims to find the sparsest solution (i.e., one with the fewest non-zero entries) to , where the full row rank matrix with generates an underdetermined system. The optimization problem is described as:

OMP works by first finding the support:

of the solution, and then solving the least squares problem:

corresponding to the support set.

MATLAB function:

x = OMP(A, y, tolerance)

Performance Guarantee

OMP is guaranteed to provide the exact solution (zero tolerance) if this solution exists, and satisfies:

where the mutual coherence measures the dependence between different columns of the system matrix, and is defined as:

Reference:

Bruckstein, Alfred M., David L. Donoho, and Michael Elad. "From sparse solutions of systems of equations to sparse modeling of signals and images." SIAM review 51.1 (2009): 34-81.