General l₁-regularized minimization problems of the form

where f is a convex, but not necessarily strictly convex, function, can be solved with a globally-convergent fixed-point iteration scheme. In addition, q-linear rates of convergence can be achieved under mild conditions.

Problems in the form of (1) are often of interest when x is expected to be sparse, or contain outliers. In compressed sensing signal reconstruction, f(x) is a weighted least-squares term. In this case, q-linear convergence rates can be shown as long as a certain reduced Hessian is full rank, or a strict complementarity condition holds. In order to obtain good practical performance, the basic fixed-point iterations should be augmented with a continuation approach. In brief, the continuation approach consists of solving (1) for an increasing sequence of μ values, using the solution at the last μ value as the starting point for the next μ value. Thus, Fixed-Point Continuation (FPC).

This software is being developed at Rice University, in the Department of Computational and Applied Mathematics. Researchers include:

• TR07-07. A Fixed-Point Continuation Method for l1-Regularized Minimization with Applications to Compressed Sensing. E. T. Hale, W. Yin and Y. Zhang.

• A fixed-point continuation algorithm for l₁-Minimization. Presented by Wotao Yin at ICCOPT-II-MOPTA 07, McMaster University, Hamilton, Ontario, August 13, 2007.
• Fixed-point continuation for compressed sensing signal reconstruction. Presented by Elaine T. Hale at the Department of Compuational and Applied Mathematics Colloquium, Rice University, September 10, 2007.

FPC 2.0 is almost identical to FPC 1.0 below except that it uses Barzilar-Borwein steps to accelerate convergence.

To use the code, unzip fpc_v2.zip to a folder. Two driver MATLAB scripts for running simulated compressed sensing recovery problems are provided in the folder drivers.

[Download here]

Check out the recent FPC_AS [link]
It is better on CS problems with solutions that are sparse and/or have high dynamic ranges.
For problems with noisy measurements or compressible solutions, please use an alternative set of parameters given in its manual.

FPC 1.0 is Matlab code for solving problems (1) when f(x) = 0.5 ||Ax - b||_M². In addition, there is code for generating A and b for basic compressed sensing scenarios, for calculating M and μ when b = Ax and either or both x and b are corrupted with i.i.d. Gaussian noise, and de-biasing.

To use the code, unzip the fpc folder and add it and its folders to your Matlab path. A basic script for running single simulated compressed sensing recovery problems is provided in the main folder, one_run.m.

[Download here]
Check out the recent FPC_AS [link]