Average Case Analysis of High-Dimensional Block-Sparse Recovery and Regression for Arbitrary Designs

Waheed Bajwa, Marco Duarte, Robert Calderbank
Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, PMLR 33:57-67, 2014.

Abstract

This paper studies conditions for high-dimensional inference when the set of observations is given by a linear combination of a small number of groups of columns of a design matrix, termed the “block-sparse” case. In this regard, it first specifies conditions on the design matrix under which most of its block submatrices are well conditioned. It then leverages this result for average-case analysis of high-dimensional block-sparse recovery and regression. In contrast to earlier works, the results of this paper are fundamentally different because (i) they provide conditions on arbitrary designs that can be explicitly computed in polynomial time, (ii) the provided conditions translate into near-optimal scaling of the number of observations with the number of active blocks of the design matrix, and (iii) they suggest that the spectral norm, rather than the column/block coherences, of the design matrix fundamentally limits the performance of computational methods in high-dimensional settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v33-bajwa14, title = {{Average Case Analysis of High-Dimensional Block-Sparse Recovery and Regression for Arbitrary Designs}}, author = {Bajwa, Waheed and Duarte, Marco and Calderbank, Robert}, booktitle = {Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics}, pages = {57--67}, year = {2014}, editor = {Kaski, Samuel and Corander, Jukka}, volume = {33}, series = {Proceedings of Machine Learning Research}, address = {Reykjavik, Iceland}, month = {22--25 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v33/bajwa14.pdf}, url = {https://proceedings.mlr.press/v33/bajwa14.html}, abstract = {This paper studies conditions for high-dimensional inference when the set of observations is given by a linear combination of a small number of groups of columns of a design matrix, termed the “block-sparse” case. In this regard, it first specifies conditions on the design matrix under which most of its block submatrices are well conditioned. It then leverages this result for average-case analysis of high-dimensional block-sparse recovery and regression. In contrast to earlier works, the results of this paper are fundamentally different because (i) they provide conditions on arbitrary designs that can be explicitly computed in polynomial time, (ii) the provided conditions translate into near-optimal scaling of the number of observations with the number of active blocks of the design matrix, and (iii) they suggest that the spectral norm, rather than the column/block coherences, of the design matrix fundamentally limits the performance of computational methods in high-dimensional settings.} }
Endnote
%0 Conference Paper %T Average Case Analysis of High-Dimensional Block-Sparse Recovery and Regression for Arbitrary Designs %A Waheed Bajwa %A Marco Duarte %A Robert Calderbank %B Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2014 %E Samuel Kaski %E Jukka Corander %F pmlr-v33-bajwa14 %I PMLR %P 57--67 %U https://proceedings.mlr.press/v33/bajwa14.html %V 33 %X This paper studies conditions for high-dimensional inference when the set of observations is given by a linear combination of a small number of groups of columns of a design matrix, termed the “block-sparse” case. In this regard, it first specifies conditions on the design matrix under which most of its block submatrices are well conditioned. It then leverages this result for average-case analysis of high-dimensional block-sparse recovery and regression. In contrast to earlier works, the results of this paper are fundamentally different because (i) they provide conditions on arbitrary designs that can be explicitly computed in polynomial time, (ii) the provided conditions translate into near-optimal scaling of the number of observations with the number of active blocks of the design matrix, and (iii) they suggest that the spectral norm, rather than the column/block coherences, of the design matrix fundamentally limits the performance of computational methods in high-dimensional settings.
RIS
TY - CPAPER TI - Average Case Analysis of High-Dimensional Block-Sparse Recovery and Regression for Arbitrary Designs AU - Waheed Bajwa AU - Marco Duarte AU - Robert Calderbank BT - Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics DA - 2014/04/02 ED - Samuel Kaski ED - Jukka Corander ID - pmlr-v33-bajwa14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 33 SP - 57 EP - 67 L1 - http://proceedings.mlr.press/v33/bajwa14.pdf UR - https://proceedings.mlr.press/v33/bajwa14.html AB - This paper studies conditions for high-dimensional inference when the set of observations is given by a linear combination of a small number of groups of columns of a design matrix, termed the “block-sparse” case. In this regard, it first specifies conditions on the design matrix under which most of its block submatrices are well conditioned. It then leverages this result for average-case analysis of high-dimensional block-sparse recovery and regression. In contrast to earlier works, the results of this paper are fundamentally different because (i) they provide conditions on arbitrary designs that can be explicitly computed in polynomial time, (ii) the provided conditions translate into near-optimal scaling of the number of observations with the number of active blocks of the design matrix, and (iii) they suggest that the spectral norm, rather than the column/block coherences, of the design matrix fundamentally limits the performance of computational methods in high-dimensional settings. ER -
APA
Bajwa, W., Duarte, M. & Calderbank, R.. (2014). Average Case Analysis of High-Dimensional Block-Sparse Recovery and Regression for Arbitrary Designs. Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 33:57-67 Available from https://proceedings.mlr.press/v33/bajwa14.html.

Related Material