Fixed-Point Continuation (FPC)
An algorithm for large-scale image and data processing applications of
l_{1}-minimization | |||||

| |||||

Abstract
General
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). | |||||

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

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

Presentations
- A fixed-point continuation
algorithm for
*l*_{1}-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.
| |||||

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 fpc_v2.zip to a folder. Two driver MATLAB scripts for running simulated compressed sensing recovery
problems are provided in the folder
Check out the recent FPC_AS [link] | |||||

Version 1.0, 9/11/2007
FPC 1.0 is Matlab code for solving problems (1) when
f(x) = 0.5 ||Ax - b|| 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] |