Publications [#335332] of Robert Calderbank

Conference articles PUBLISHED

1. Bajwa, WU; Duarte, MF; Calderbank, R, Average case analysis of high-dimensional block-sparse recovery and regression for arbitrary designs, Journal of Machine Learning Research, vol. 33 (January, 2014), pp. 57-67
   (last updated on 2026/01/17)

   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: (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.