Category:Misc Solvers

From SparseSolver

These solvers do not fit into other categories, or else they are waiting to be categorized.

Contents 1 IHT 2 Smoothing l0 quasi-norm 3 Coordinate Descent 4 Special Applications 4.1 MRI 5 Uncategorized 6 References

IHT

The simplest algorithm is iterative hard-thresholding (IHT)^[1] which directly tries to solve the best subset selection problem. It has been analyzed and can provide some recovery guarantees. Thomas Blumensath has a collection of greedy and hard thresholding algorithms (GreedLab and HardLab).

ALPS is an accelerated variant of IHT, and CLASH is a variant that also includes l1 norm constraints and has some provable recovery guarantees.

Smoothing l0 quasi-norm

The SL0 method attempts to smooth the l0 quasi-norm and thus approximately solve the best subset selection problem.

Coordinate Descent

A coordinate descent algorithm for l1 functions is proposed in ^[2]

Special Applications

MRI

• sparseMRI by Michael Lustig and Stanford co-authors. For MRI.
• l1-spirit by Michael Lustig. This is custom for MRI reconstruction, and is very well-done code (MATLAB, which calls mex files and can call CUDA executables to take advantage of a fast graphics card).

Uncategorized

• KF-CS: Kalman Filtered CS (and other sequential CS algorithms)
• k-t FOCUSS. FOCUSS is a type of iteratively-reweighted least-squares (IRLS).
• Cycling matching pursuit (CMP)] with code. They say it's similar to OMP

References

1. ↑ T. Blumensath, M. E. Davies, Iterative hard thresholding for compressed sensing, Harm. Anal. 27 (2009), no. 3, 265--274. arXiv:0805.0510
2. ↑ J. Friedman, T. Hastie, and R. Tibshirani, Regularization paths for generalized linear models via coordinate descent, J. Stat. Software 33 (2010), no. 1.