Matching pursuit

Summary

Matching pursuit is a greedy algorithm that builds an approximation of a vector from a dictionary of unit vectors, one element at a time. At each step it picks the dictionary element most correlated with the current residual and removes the projection of the residual on that element. It gives a cheap way to compute n-term approximations and sparse approximations when the exact problem is too hard. A variant, orthogonal matching pursuit, re-projects onto all chosen elements at each step.