Fixed-Point Continuation (FPC)
An algorithm for large-scale image and data processing applications of l1-minimization
Abstract People Papers Presentations Software

General l1-regularized minimization problems of the form

(1) min ||x||1 + μ f(x),

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:

Elaine T. Hale Wotao Yin Yin Zhang
Version 2.0 (with Barzilai-Borwein steps), 6/13/2008

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 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.

Version 1.0, 9/11/2007

FPC 1.0 is Matlab code for solving problems (1) when f(x) = 0.5 ||Ax - b||M2. 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]