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

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.

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