A totally unimodular view of structured sparsity

Marwa El Halabi, Volkan Cevher
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:223-231, 2015.

Abstract

This paper describes a simple framework for structured sparse recovery based on convex optimization. We show that many structured sparsity models can be naturally represented by linear matrix inequalities on the support of the unknown parameters, where the constraint matrix has a totally unimodular (TU) structure. For such structured models, tight convex relaxations can be obtained in polynomial time via linear programming. Our modeling framework unifies the prevalent structured sparsity norms in the literature, introduces new interesting ones, and renders their tightness and tractability arguments transparent.

Cite this Paper

BibTeX
@InProceedings{pmlr-v38-elhalabi15, title = {{A totally unimodular view of structured sparsity}}, author = {El Halabi, Marwa and Cevher, Volkan}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {223--231}, 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/elhalabi15.pdf}, url = {https://proceedings.mlr.press/v38/elhalabi15.html}, abstract = {This paper describes a simple framework for structured sparse recovery based on convex optimization. We show that many structured sparsity models can be naturally represented by linear matrix inequalities on the support of the unknown parameters, where the constraint matrix has a totally unimodular (TU) structure. For such structured models, tight convex relaxations can be obtained in polynomial time via linear programming. Our modeling framework unifies the prevalent structured sparsity norms in the literature, introduces new interesting ones, and renders their tightness and tractability arguments transparent.} }
Endnote
%0 Conference Paper %T A totally unimodular view of structured sparsity %A Marwa El Halabi %A Volkan Cevher %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-elhalabi15 %I PMLR %P 223--231 %U https://proceedings.mlr.press/v38/elhalabi15.html %V 38 %X This paper describes a simple framework for structured sparse recovery based on convex optimization. We show that many structured sparsity models can be naturally represented by linear matrix inequalities on the support of the unknown parameters, where the constraint matrix has a totally unimodular (TU) structure. For such structured models, tight convex relaxations can be obtained in polynomial time via linear programming. Our modeling framework unifies the prevalent structured sparsity norms in the literature, introduces new interesting ones, and renders their tightness and tractability arguments transparent.
RIS
TY - CPAPER TI - A totally unimodular view of structured sparsity AU - Marwa El Halabi AU - Volkan Cevher 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-elhalabi15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 223 EP - 231 L1 - http://proceedings.mlr.press/v38/elhalabi15.pdf UR - https://proceedings.mlr.press/v38/elhalabi15.html AB - This paper describes a simple framework for structured sparse recovery based on convex optimization. We show that many structured sparsity models can be naturally represented by linear matrix inequalities on the support of the unknown parameters, where the constraint matrix has a totally unimodular (TU) structure. For such structured models, tight convex relaxations can be obtained in polynomial time via linear programming. Our modeling framework unifies the prevalent structured sparsity norms in the literature, introduces new interesting ones, and renders their tightness and tractability arguments transparent. ER -
APA
El Halabi, M. & Cevher, V.. (2015). A totally unimodular view of structured sparsity. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:223-231 Available from https://proceedings.mlr.press/v38/elhalabi15.html.

Related Material