The zeroSR1 toolbox implements the algorithm from 'A quasi-Newton proximal splitting method' by Stephen Becker and Jalal Fadili, which appeared in NIPS 2012. The paper is available at arXiv 1206.1156.
Briefly, the algorithm follows the standard proximal-gradient method, but allows a scaled prox. This enables us to use a limited-memory SR1 method (similar to L-BFGS).
The algorithm solves problems of the form min_x f(x) + h(x) where f is differentiable (more precisely, with a Lipschitz gradient) and h is one of the following (see the paper):
| Available "h" | Cost for input of size "n" |
|---|---|
| l1 norm | O( n log n) |
| non-negativity constraints | O( n log n) |
| l1 and non-negativity | O( n log n) |
| box constraints | O( n log n ) |
| l_infinity norm constraint | O( n log n ) |
| hinge loss | O( n log n ) |
The algorithm compares favorably with other methods, including L-BFGS-B.
This toolbox currently implements in the following languages
- Matlab
- Octave
Further releases may target these languages:
- Python
- R
- C++
For Matlab, there is no installation necessary. Every time you run a new Matlab session, run the setup_zeroSR1.m file and it will add the correct paths.
Run tests/test_solver_simple.m to see how to solve a typical problem
In each folder, see they Contents.m file for more information
This includes the zeroSR1 algorithm as well as implemenations of FISTA and other proximal-gradient methods
The scaled diagonal+ rank1 prox operators for various "g" functions
These are pre-made wrappers for the various smooth "f" functions. The files here with the _splitting suffix are intended for use with any method that requires forming the augmented variable "x_aug = (x_pos, x_neg)". For example, this approach is used when using L-BFGS-B (which only allows box constraints, such as x_pos >= 0, x_neg <= 0) to solve the LASSO problem.
Helper files
Verify the algorithm and proxes are working correctly. This uses CVX to verify; if this is not installed on your system, then it relies on precomputed solutions stored in a subdirectory.
Recreate tests of several algorithms, or do something more interesting than the scripts in tests
The original authors are Stephen Becker and Jalal Fadili. Further contributions are welcome.