| Paper: | SPTM-P9.12 | ||
| Session: | Signal Restoration, Reconstruction and Enhancement | ||
| Time: | Thursday, May 18, 14:00 - 16:00 | ||
| Presentation: | Poster | ||
| Topic: | Signal Processing Theory and Methods: Signal Restoration, Reconstruction, and Enhancement | ||
| Title: | Solution of l1 Minimization Problems by LARS/homotopy Methods | ||
| Authors: | Iddo Drori, David Donoho, Stanford University, United States | ||
| Abstract: | Many applications in signal processing lead to the optimization problems \[ \quad \min \| x \|_1 \mbox{ subject to } y = Ax , \] and \[ \quad \min \| x \|_1 \mbox{ subject to } \|y - Ax\| \leq \varepsilon , \] where $A$ is a given $d$ times $n$ matrix, $d < n$, and $y$ is a given $n \times 1$ vector. In this work we consider $\ell_1$ minimization by using LARS, Lasso, and homotopy methods \cite{LARS,LASSO,Osborne} (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)$. | ||
©2018 Conference Management Services, Inc. -||- email: webmaster@icassp2006.org -||- Last updated Friday, August 17, 2012