## Abstract

We consider the ℓ _{1}-regularized least-squares problem for sparse recovery and compressed sensing. Since the objective function is not strongly convex, standard proximal gradient methods only achieve sublinear convergence. We propose a homotopy continuation strategy, which employs a proximal gradient method to solve the problem with a sequence of decreasing regularization parameters. It is shown that under common assumptions in compressed sensing, the proposed method ensures that all iterates along the homotopy solution path are sparse, and the objective function is effectively strongly convex along the solution path. This observation allows us to obtain a global geometric convergence rate for the procedure. Empirical results are presented to support our theoretical analysis.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 29th International Conference on Machine Learning, ICML 2012 |

Pages | 839-846 |

Number of pages | 8 |

State | Published - 2012 |

Externally published | Yes |

Event | 29th International Conference on Machine Learning, ICML 2012 - Edinburgh, United Kingdom Duration: Jun 26 2012 → Jul 1 2012 |

### Publication series

Name | Proceedings of the 29th International Conference on Machine Learning, ICML 2012 |
---|---|

Volume | 1 |

### Other

Other | 29th International Conference on Machine Learning, ICML 2012 |
---|---|

Country/Territory | United Kingdom |

City | Edinburgh |

Period | 6/26/12 → 7/1/12 |

## ASJC Scopus subject areas

- Human-Computer Interaction
- Education

## Fingerprint

Dive into the research topics of 'A proximal-gradient homotopy method for the ℓ_{1}-regularized least-squares problem'. Together they form a unique fingerprint.