FPC_AS
A MATLAB Solver for L1-Regularization Problems

Introduction

FPC_AS (fixed-point continuation and active set) is a MATLAB solver for the l1-regularized least squares problem

minimizex mu||x||1 + (1/2)||Ax-b||22,

where the parameter mu, the matrix A, and the vector b are given. This problem arises in compressed sensing to recover a sparse vector x* from a set of linear measurements b=Ax* or b=Ax*+n, where n is noise. The measurements can be incomplete (or undersampled) to certain degree in the sense that b has less number of components than x.

This solver can also solve the contrained problem

minimizex ||x||1,  subject to  Ax=b,

if mu is set to be a tiny value (e.g., 1E-10).

For more information about the theory and applications of these problems, see the review article [pdf].

Extension

With non-essential modifications, the solver can also solve the general l1-regularization problem

minimizex mu||x||1 + f(x),

for a convex, differentiable function f.

History

FPC_AS is a successor of FPC [link]. While FPC_AS still performs shrinkage iterations and continuation as its predecessor, most of the code has been rewritten. Compared to FPC, which has good performance on large-scale problems with highly sparse solutions, FPC_AS works better overall and much better on certain difficult problems arising in compressed sensing, to name a few, those with sparse, but not highly sparse, solutions and those whose solutions have both very large and very small nonzero components (i.e., the solutions have huge dynamic ranges). These problems are difficult because it is hard to identify certain nonzero components in the solutions as these components are either too small or have only slight advantage to represent b over some of the others. FPC_AS was designed with active set identification and sub-optimization to help recover these components in the solutions.

For sparse/compressible signal recovery from noisy measurements, FPC (version 2.0, with Barzilai-Borwein steps) may still be faster than FPC_AS.

Two Papers

Algorithm and simulations: [pdf], by Z. Wen, W. Yin, D. Goldfarb, and Y. Zhang.

Convergence: [pdf], by Z. Wen, W. Yin, H. Zhang, and D. Goldfarb.

Download

Latest Version 1.21 (July 06, 2010). Stability improved. [download]
Previous Version 1.2 (June 27, 2010). Bugs fixed.
Previous Version 1.1 (April 29, 2009).
Previous Version 1.0 (September 5, 2008).
  • Notice: Function PCG of MATLAB (at least for 2008a and earlier versions) performs two matrix-vector multiplications at each iteration, in which only one is needed. Therefore, PCG was modified and saved as WPCG under src/private in FPC_AS 1.1.
  • Important: if FPC_AS fails, please switch subproblem solver from MATLAB's pcg to lbfgs-b.
  • Contents: FPC_AS solver, test problems, MATLAB class A_operator, FPC's problem generator
  • Language: MATLAB (tested on versions 2007a/b, 2008a)
  • User Manual: [pdf]
  • Code Authors:
    • Zaiwen Wen [link], IEOR, Columbia University
    • Wotao Yin [link], CAAM, Rice University

License

FPC_AS Copyright (C) 2008, Zaiwen Wen, Wotao Yin

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.

Related Software and Links