These non-convex solvers look at local structure to determine the next iteration. The canonical algorithm is matching pursuits, and the simplest algorithm that is actually useful in practice is orthogonal matching pursuits OMP. See the OMP page for an introduction. See  for a review paper as of December 2008.
Improvements over OMP include:
- StOMP (Stagewise OMP) 
- ROMP (Robust OMP) 
- CoSaMP (Compressive Sampling Matching Pursuit)
- Sparse Matching Pursuits
- SPAMS includes an excellent implementation of OMP
- SparseLab includes an implementation of OMP
- Scikit-learn includes an efficient Python implementation of OMP.
Extensions to matrix variables
Other greedy algorithms
- ↑ S. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Trans. Sig. Proc. 41 (1993), 3397--3415.
- ↑ J. A. Tropp and A. C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Tran. Info. Theory 53 (2007), no. 12.
- ↑ 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.
- ↑ J. A. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Inform. Theory 50 (2004), 2231--2242.
- ↑ D. Needell, J. A. Tropp, R. Vershynin, Greedy Signal Recovery Review, in Proc. Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA Oct. 2008 arXiv:0812.2202
- ↑ D. L. Donoho, Y. Tsaig, I. Drori, and J.-L. Starck, Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit, Technical report, 2006. link
- ↑ D. Needell and R. Vershynin, Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, Found. Comp. Math. 9 (2009), no. 3, 371--334.
- ↑ D. Needell and R. Vershynin, Signal recovery from inaccurate and incomplete measurements via regularized orthogonal matching pursuit, IEEE J. Sel. Topics Sig. Proc. 4 (2010), 310--316.
- ↑ D. Needell and J. A. Tropp, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal. 26 (2009), 301--321. arXiv:0902.0026