l1_ls: Simple Matlab Solver for l1-regularized Least Squares Problems

Version Beta (Apr 2008)
Kwangmoo Koh, Seung-Jean Kim, and Stephen Boyd

Purpose

l1_ls is a Matlab implementation of the interior-point method for ell_1-regularized least squares described in the paper A Method for Large-Scale l1-Regularized Least Squares. l1_ls solves an optimization problem of the form

mbox{minimize } |Ax-y|_2^2+lambda|x|_1,

where the variable is xinmathbf{R}^{n}, and the problem data are Ainmathbf{R}^{mtimes n}, yinmathbf{R}^{m} and lambdainmathbf{R}_{+}^{n}. Another version of l1_ls handles the same problem, with the additional constraint that x is nonnegative.

l1_ls is developed for large problems. It can solve large sparse problems with a million variables with high accuracy in a few tens of minutes on a PC. It can also efficiently solve very large dense problems, that arise in sparse signal recovery with orthogonal transforms, by exploiting fast algorithms for these transforms.

Feedback

Please report any bugs to Kwangmoo Koh <deneb1@stanford.edu>, Seung-Jean Kim <sjkim@stanford.edu> or Stephen Boyd <boyd@stanford.edu>.

Download

l1_ls is distributed under the terms of the GNU General Public License 2.0.

Boyd’s research group page.