This is a simple and extremely efficient iterative methods for solving the Basis Pursuit problemmin ||x||1, subject to Ax = b,
which is used in compressed sensing. This method is based on Bregman iterative regularization and it gives a very accurate solution after solving only a very small number of instances of the unconstrained problemmin p||x||1 + (1/2)||Ax - fk||2,
for given matrix A and vector fk. Our approach is especially useful for many compressed sensing applications where matrix-vector operations involving A and AT can be computed by fast transforms.
The current expectation is that this algorithm is much faster than linear programming. At some point, it needs to be benchmarked against other codes.
In another area dealing with nuclear norm minimization featured recently here and there. There is a
presentation entitled Interior-point methods for nuclear norm minimization by Zhang Liu and Lieven Vandenberghe presented at HPOPT 2008.
They feature CVXOPT described as :
CVXOPT is a free software package for convex optimization based on the Python programming language. It can be used with the interactive Python interpreter, on the command line by executing Python scripts, or integrated in other software via Python extension modules. Its main purpose is to make the development of software for convex optimization applications straightforward by building on Python's extensive standard library and on the strengths of Python as a high-level programming language
SPGL1 is a Matlab solver for large-scale one-norm regularized least squares. It is designed to solve any of the following three problems:
Basis pursuit denoise
(BP)minimizex1subject toAx−b2
Basis pursuit
(BP)minimizex1subject toAx=b
Lasso
(Lasso)minimizeAx−b2subject tox1
SPGL1 relies only on matrix-vector operations
Ax andATy and accepts both explicit matrices and functions that evaluate these products. SPGL1 is suitable for problems that are in the complex domain.The theory underlying SPGL1 is described in the paper Probing the Pareto Frontier for basis pursuit solutions (pdf).
No comments:
Post a Comment