Fixed-Point Continuation (FPC)
An algorithm for large-scale applications of L1-minimization
Abstract
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).
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 l1-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 Computational and Applied Mathematics Colloquium, Rice University, September 10, 2007.
Software
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.