Timezone: »

 
Poster
An Homotopy Algorithm for the Lasso with Online Observations
Pierre Garrigues · Laurent El Ghaoui

Mon Dec 08 08:45 PM -- 12:00 AM (PST) @ None #None
It has been shown that the problem of $\ell_1$-penalized least-square regression commonly referred to as the Lasso or Basis Pursuit DeNoising leads to solutions that are sparse and therefore achieves model selection. We propose in this paper an algorithm to solve the Lasso with online observations. We introduce an optimization problem that allows us to compute an homotopy from the current solution to the solution after observing a new data point. We compare our method to Lars and present an application to compressed sensing with sequential observations. Our approach can also be easily extended to compute an homotopy from the current solution to the solution after removing a data point, which leads to an efficient algorithm for leave-one-out cross-validation.

Author Information

Pierre Garrigues (IQ Engines Inc.)
Laurent El Ghaoui (University of California at Berkeley)

More from the Same Authors