Nuit Blanche: l1_ls: Simple Matlab Solver for l1-regularized Least Squares Problems (compressed sensing)

Saturday, March 17, 2007

l1_ls: Simple Matlab Solver for l1-regularized Least Squares Problems (compressed sensing)

Make that four codes available to perform reconstruction in the compressed sensing setting. Kwangmoo Koh, Seung-Jean Kim, and Stephen Boyd just made available l1_ls. According to the authors:

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

l1_ls is a Matlab implementation of the interior-point method for l1-regularized least squares described in the paper, A Method for Large-Scale l1-Regularized Least Squares Problems with Applications in Signal Processing and Statistics. l1_ls solves an optimization problem of the form

$\begin{array}{ll}\mbox{minimize} & \|Ax-y\|_2^2+\lambda\|x\|_1 \end{array}$ ,

where the variable is $x\in\mathbf{R}^{n}$ and the problem data are $A\in\mathbf{R}^{m\times n}$ , $y\in\mathbf{R}^{m}$ and $\lambda\in\mathbf{R}_{+}^{n}$ .

The solver 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.