Category:Solvers

From SparseSolver

N.B. The upper portion of this page is editable, but the lower portion is an automatically generated list that links to all other pages when have been included in the Solvers category. To add a page to this category, put the following code somewhere in the page: [[Category:Solvers]]. We also encourage using the solver template: this provides a little info box. To use it, just follow the example at Template:Solver and insert that code anywhere in the new page. You can also edit the solver template to add or modify fields or change the style of the info box.

This page will not discuss solvers themselves, rather just list them, since there are too many to discuss in one place. In the subcategory pages, a brief description of the solvers will be hand-generated, followed by automatically-generated links to the solver pages for more details. Right now, the first-order (convex) method page and the matrix completion solvers have the most information.

Most solvers are written in Matlab or C/C++. Algorithms listed in other languages are listed as well on special pages, such as Category:R Solvers and Category:Python Solvers.

Surveys

In addition to internet resources, here is a list of some review papers on solvers (please add to this list!):

• Tropp and Wright, 2010 review article ^[1]
• Bob Sturm (see arXiv:1103.6246) tests algorithms on different distributions of random vectors, for N=40, using a Gaussian sensing matrix and noiseless measurements. The algorithms tested are:
  • Greedy: OMP, PrOMP, ROMP, StOMP
  • Thresholding: IST, IHT, CoSaMP, subspace pursuit SP, two-stage thresholding TST, AMP, ALPS
  • Convex relaxation: BP (via CVX), LAG formulation via GPSR, reweighted l1 IRL1
  • Non-convex relaxation: SL0
• Pope, 2009 Master's thesis ^[2]
• Loris, 2009 article ^[3]
• Schmidt, Fung and Rosaless, 2009 review article ^[4] for l1 regularized problems (e.g. for machine learning), and a set of codes called l1General.
• Yuan et al. 2010 review ^[5]

Code packages that implement many algorithms

These are generally not packages with new algorithms, but rather packages incorporating several well-known existing algorithms, perhaps with a few improvements

• SPAMS in C, with Matlab and other interfaces. GPL license.
• KL1p: Sparse Recovery of Underdetermined Inverse Problems, in C++. LGPL license. Includes Basis Pursuit (perhaps using an algorithm like in L1-magic?), OMP, ROMP, CoSaMP (see Greedy Solvers), subspace pursuits, SL0, AMP, Expectation Maximization Belief Propagation. Details.

References

1. ↑ J. A. Tropp and S. J. Wright, Computational methods for sparse solution of linear inverse problems, Proc. IEEE 98 (2010), no. 6, 948--958. link
2. ↑ G. Pope, Compressive sensing: A summary of reconstruction algorithms, Master's thesis, ETH, Zurich, Feb. 2009. link
3. ↑ I. Loris, On the performance of algorithms for the minimization of 11-penalized functionals, Inverse Problems 25 (2009). arXiv:0710.4082
4. ↑ M. Schmidt, G. Fung and R. Rosaless, Reviewing optimization methods for L1-regularized optimization, 2009. link, codes
5. ↑ Guo-Xun Yuan, Kai-Wei Chang, Cho-Jui Hsieh and Chih-Jen Lin, A Comparison of Optimization Methods and Software for Large-scale L1-regularized Linear Classification, Journal of Machine Learning Research 11 (2010) 3183-3234 paper