Presentation
Average Case Analysis of High-Dimensional Block-Sparse Recovery and Regression for Arbitrary Designs
International Conference on Artificial Intelligence and Statistics (AISTATS)
(2014)
Abstract
This paper studies conditions for highdimensional 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 rst speci es 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: (i) this paper provides 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) the conditions 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.
Disciplines
Publication Date
2014
Comments
This is an author manuscript of this conference paper. More information about the conference can be found at http://www.aistats.org/aistats2014/
Citation Information
Waheed U. Bajwa, Marco Duarte and Robert Calderbank. "Average Case Analysis of High-Dimensional Block-Sparse Recovery and Regression for Arbitrary Designs" International Conference on Artificial Intelligence and Statistics (AISTATS) (2014) Available at: http://works.bepress.com/marco_duarte/14/