A MATLAB Solver for L1-Regularization Problems


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