A Fast Algorithm for Recovery of Jointly Sparse Vectors based on the Alternating Direction Methods

Hongtao Lu, Xianzhong Long, Jingyuan Lv
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:461-469, 2011.

Abstract

The standard compressive sensing (CS) aims to recover sparse signal from single measurement vector (SMV) which is known as SMV model. In this paper, we consider the recovery of jointly sparse signals in the multiple measurement vector (MMV) scenario where signal is represented as a matrix and the sparsity of signal occurs in a common location set. The sparse MMV model can be formulated as a matrix $(2,1)$-norm minimization problem. However, the $(2,1)$-norm minimization problem is much more difficult to solve than l1-norm minimization. In this paper, we propose a very fast algorithm, called MMV-ADM, for jointly sparse signal recovery in MMV settings based on the alternating direction method (ADM). The MMV-ADM alternately updates the signal matrix, the Lagrangian multiplier and the residue, and all update rules only involve matrix or vector multiplications and summations, so it is simple, easy to implement and much more fast than the state-of-the-art method MMVprox. Numerical simulations show that MMV-ADM is at least dozens of times faster than MMVprox with comparable recovery accuracy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-lu11a, title = {A Fast Algorithm for Recovery of Jointly Sparse Vectors based on the Alternating Direction Methods}, author = {Lu, Hongtao and Long, Xianzhong and Lv, Jingyuan}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {461--469}, year = {2011}, editor = {Gordon, Geoffrey and Dunson, David and Dudík, Miroslav}, volume = {15}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {11--13 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v15/lu11a/lu11a.pdf}, url = {https://proceedings.mlr.press/v15/lu11a.html}, abstract = {The standard compressive sensing (CS) aims to recover sparse signal from single measurement vector (SMV) which is known as SMV model. In this paper, we consider the recovery of jointly sparse signals in the multiple measurement vector (MMV) scenario where signal is represented as a matrix and the sparsity of signal occurs in a common location set. The sparse MMV model can be formulated as a matrix $(2,1)$-norm minimization problem. However, the $(2,1)$-norm minimization problem is much more difficult to solve than l1-norm minimization. In this paper, we propose a very fast algorithm, called MMV-ADM, for jointly sparse signal recovery in MMV settings based on the alternating direction method (ADM). The MMV-ADM alternately updates the signal matrix, the Lagrangian multiplier and the residue, and all update rules only involve matrix or vector multiplications and summations, so it is simple, easy to implement and much more fast than the state-of-the-art method MMVprox. Numerical simulations show that MMV-ADM is at least dozens of times faster than MMVprox with comparable recovery accuracy.} }
Endnote
%0 Conference Paper %T A Fast Algorithm for Recovery of Jointly Sparse Vectors based on the Alternating Direction Methods %A Hongtao Lu %A Xianzhong Long %A Jingyuan Lv %B Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2011 %E Geoffrey Gordon %E David Dunson %E Miroslav Dudík %F pmlr-v15-lu11a %I PMLR %P 461--469 %U https://proceedings.mlr.press/v15/lu11a.html %V 15 %X The standard compressive sensing (CS) aims to recover sparse signal from single measurement vector (SMV) which is known as SMV model. In this paper, we consider the recovery of jointly sparse signals in the multiple measurement vector (MMV) scenario where signal is represented as a matrix and the sparsity of signal occurs in a common location set. The sparse MMV model can be formulated as a matrix $(2,1)$-norm minimization problem. However, the $(2,1)$-norm minimization problem is much more difficult to solve than l1-norm minimization. In this paper, we propose a very fast algorithm, called MMV-ADM, for jointly sparse signal recovery in MMV settings based on the alternating direction method (ADM). The MMV-ADM alternately updates the signal matrix, the Lagrangian multiplier and the residue, and all update rules only involve matrix or vector multiplications and summations, so it is simple, easy to implement and much more fast than the state-of-the-art method MMVprox. Numerical simulations show that MMV-ADM is at least dozens of times faster than MMVprox with comparable recovery accuracy.
RIS
TY - CPAPER TI - A Fast Algorithm for Recovery of Jointly Sparse Vectors based on the Alternating Direction Methods AU - Hongtao Lu AU - Xianzhong Long AU - Jingyuan Lv BT - Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics DA - 2011/06/14 ED - Geoffrey Gordon ED - David Dunson ED - Miroslav Dudík ID - pmlr-v15-lu11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 461 EP - 469 L1 - http://proceedings.mlr.press/v15/lu11a/lu11a.pdf UR - https://proceedings.mlr.press/v15/lu11a.html AB - The standard compressive sensing (CS) aims to recover sparse signal from single measurement vector (SMV) which is known as SMV model. In this paper, we consider the recovery of jointly sparse signals in the multiple measurement vector (MMV) scenario where signal is represented as a matrix and the sparsity of signal occurs in a common location set. The sparse MMV model can be formulated as a matrix $(2,1)$-norm minimization problem. However, the $(2,1)$-norm minimization problem is much more difficult to solve than l1-norm minimization. In this paper, we propose a very fast algorithm, called MMV-ADM, for jointly sparse signal recovery in MMV settings based on the alternating direction method (ADM). The MMV-ADM alternately updates the signal matrix, the Lagrangian multiplier and the residue, and all update rules only involve matrix or vector multiplications and summations, so it is simple, easy to implement and much more fast than the state-of-the-art method MMVprox. Numerical simulations show that MMV-ADM is at least dozens of times faster than MMVprox with comparable recovery accuracy. ER -
APA
Lu, H., Long, X. & Lv, J.. (2011). A Fast Algorithm for Recovery of Jointly Sparse Vectors based on the Alternating Direction Methods. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:461-469 Available from https://proceedings.mlr.press/v15/lu11a.html.

Related Material