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.


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.

Related Material