Abstract: Many applications in signal processing lead to the optimization problems min ||x||_1 subject to y = Ax, and min ||x||_1 subject to ||y - Ax|| < epsilon, where A is a given d times n matrix, d < n, and y is a given n vector. In this work we consider L1 minimization by using LARS, Lasso, and homotopy methods (Efron et el., Tibshirani, Osborne et al.). While these methods were first proposed for use in statistical model selection, we show that under certain conditions these methods find the sparsest solution rapidly, as opposed to conventional general purpose optimizers which are prohibitively slow. We define a phase transition diagram which shows how algorithms behave for random problems, as the ratio of unknowns to equations and the ratio of the sparsity to equations varies. We find that whenever the number k of nonzeros in the sparsest solution is less than d/2log(n) then LARS/homotopy obtains the sparsest solution in k steps each of complexity O(d^2).
@inproceedings{Drori06SolutionL1,
author = {Iddo Drori and David L. Donoho},
title = {Solution of L1 Minimization Problems by LARS/Homotopy Methods},
booktitle = {IEEE International Conference on Acoustics, Speech, and Signal Processing},
year = {2006}
}