A Simple Homotopy Algorithm for Compressive Sensing

Lijun Zhang, Tianbao Yang, Rong Jin, Zhi-Hua Zhou
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:1116-1124, 2015.

Abstract

In this paper, we consider the problem of recovering the s largest elements of an arbitrary vector from noisy measurements. Inspired by previous work, we develop an homotopy algorithm which solves the \ell_1-regularized least square problem for a sequence of decreasing values of the regularization parameter. Compared to the previous method, our algorithm is more efficient in the sense it only updates the solution once for each intermediate problem, and more practical in the sense it has a simple stopping criterion by checking the sparsity of the intermediate solution. Theoretical analysis reveals that our method enjoys a linear convergence rate in reducing the recovery error. Furthermore, our guarantee for recovering the top s elements of the target vector is tighter than previous results, and that for recovering the target vector itself matches the state of the art in compressive sensing.

Cite this Paper

BibTeX
@InProceedings{pmlr-v38-zhang15, title = {{A Simple Homotopy Algorithm for Compressive Sensing}}, author = {Zhang, Lijun and Yang, Tianbao and Jin, Rong and Zhou, Zhi-Hua}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {1116--1124}, year = {2015}, editor = {Lebanon, Guy and Vishwanathan, S. V. N.}, volume = {38}, series = {Proceedings of Machine Learning Research}, address = {San Diego, California, USA}, month = {09--12 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v38/zhang15.pdf}, url = {https://proceedings.mlr.press/v38/zhang15.html}, abstract = {In this paper, we consider the problem of recovering the s largest elements of an arbitrary vector from noisy measurements. Inspired by previous work, we develop an homotopy algorithm which solves the \ell_1-regularized least square problem for a sequence of decreasing values of the regularization parameter. Compared to the previous method, our algorithm is more efficient in the sense it only updates the solution once for each intermediate problem, and more practical in the sense it has a simple stopping criterion by checking the sparsity of the intermediate solution. Theoretical analysis reveals that our method enjoys a linear convergence rate in reducing the recovery error. Furthermore, our guarantee for recovering the top s elements of the target vector is tighter than previous results, and that for recovering the target vector itself matches the state of the art in compressive sensing.} }
Endnote
%0 Conference Paper %T A Simple Homotopy Algorithm for Compressive Sensing %A Lijun Zhang %A Tianbao Yang %A Rong Jin %A Zhi-Hua Zhou %B Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2015 %E Guy Lebanon %E S. V. N. Vishwanathan %F pmlr-v38-zhang15 %I PMLR %P 1116--1124 %U https://proceedings.mlr.press/v38/zhang15.html %V 38 %X In this paper, we consider the problem of recovering the s largest elements of an arbitrary vector from noisy measurements. Inspired by previous work, we develop an homotopy algorithm which solves the \ell_1-regularized least square problem for a sequence of decreasing values of the regularization parameter. Compared to the previous method, our algorithm is more efficient in the sense it only updates the solution once for each intermediate problem, and more practical in the sense it has a simple stopping criterion by checking the sparsity of the intermediate solution. Theoretical analysis reveals that our method enjoys a linear convergence rate in reducing the recovery error. Furthermore, our guarantee for recovering the top s elements of the target vector is tighter than previous results, and that for recovering the target vector itself matches the state of the art in compressive sensing.
RIS
TY - CPAPER TI - A Simple Homotopy Algorithm for Compressive Sensing AU - Lijun Zhang AU - Tianbao Yang AU - Rong Jin AU - Zhi-Hua Zhou BT - Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics DA - 2015/02/21 ED - Guy Lebanon ED - S. V. N. Vishwanathan ID - pmlr-v38-zhang15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 1116 EP - 1124 L1 - http://proceedings.mlr.press/v38/zhang15.pdf UR - https://proceedings.mlr.press/v38/zhang15.html AB - In this paper, we consider the problem of recovering the s largest elements of an arbitrary vector from noisy measurements. Inspired by previous work, we develop an homotopy algorithm which solves the \ell_1-regularized least square problem for a sequence of decreasing values of the regularization parameter. Compared to the previous method, our algorithm is more efficient in the sense it only updates the solution once for each intermediate problem, and more practical in the sense it has a simple stopping criterion by checking the sparsity of the intermediate solution. Theoretical analysis reveals that our method enjoys a linear convergence rate in reducing the recovery error. Furthermore, our guarantee for recovering the top s elements of the target vector is tighter than previous results, and that for recovering the target vector itself matches the state of the art in compressive sensing. ER -
APA
Zhang, L., Yang, T., Jin, R. & Zhou, Z.. (2015). A Simple Homotopy Algorithm for Compressive Sensing. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:1116-1124 Available from https://proceedings.mlr.press/v38/zhang15.html.

Related Material