CS: Bregman Iterative Algorithms, CVXOPT and SPGL1

In this webpage entitled Bregman Iterative Algorithms for Constrained Compressed Sensing and Related Problems, Wotao Yin, Stanley Osher, Donald Goldfarb, Jerome Darbon are now making their codes available. You need to request it from the site (more specifically here). To recall the code description is:

This is a simple and extremely efficient iterative methods for solving the Basis Pursuit problem

min ||x||₁, 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 problem

min p||x||₁ + (1/2)||Ax - f^k||²,
for given matrix A and vector f^k. Our approach is especially useful for many compressed sensing applications where matrix-vector operations involving A and A^T 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 now at version 1.5. From the webpage:

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 and ATy 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).