Skip to main content

Conditioning of Random Block Subdictionaries With Applications to Block-Sparse Recovery and Regression

Publication ,  Journal Article
Bajwa, WU; Duarte, MF; Calderbank, R
Published in: IEEE Transactions on Information Theory
July 1, 2015

The linear model, in which a set of observations is assumed to be given by a linear combination of columns of a matrix (often termed a dictionary), has long been the mainstay of the statistics and signal processing literature. One particular challenge for inference under linear models is understanding the conditions on the dictionary under which reliable inference is possible. This challenge has attracted renewed attention in recent years, since many modern inference problems (e.g., high-dimensional statistics and compressed sensing) deal with the underdetermined setting, in which the number of observations is much smaller than the number of columns in the dictionary. This paper makes several contributions for this setting when the set of observations is given by a linear combination of a small number of groups of columns of the dictionary, termed the block-sparse case. First, it specifies conditions on the dictionary under which most block submatrices of the dictionary (often termed block subdictionaries) are well conditioned. This result is fundamentally different from prior work on block-sparse inference because: 1) it provides conditions that can be explicitly computed in polynomial time; 2) the given conditions translate into near-optimal scaling of the number of columns of the block subdictionaries as a function of the number of observations for a large class of dictionaries; and 3) it suggests that the spectral norm, rather than the column/block coherences of the dictionary, fundamentally limits the scaling of dimensions of the well-conditioned block subdictionaries. Second, in order to help understand the significance of this result in the context of block-sparse inference, this paper investigates the problems of block-sparse recovery and block-sparse regression in underdetermined settings. In both of these problems, this paper utilizes its result concerning conditioning of block subdictionaries and establishes that near-optimal block-sparse recovery and block-sparse regression is possible for a large class of dictionaries as long as the dictionary satisfies easily computable conditions and the coefficients describing the linear combination of groups of columns can be modeled through a mild statistical prior. Third, the paper reports extensive numerical experiments that highlight the effects of different measures of the dictionary in block-sparse inference problems.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

July 1, 2015

Volume

61

Issue

7

Start / End Page

4060 / 4079

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Bajwa, W. U., Duarte, M. F., & Calderbank, R. (2015). Conditioning of Random Block Subdictionaries With Applications to Block-Sparse Recovery and Regression. IEEE Transactions on Information Theory, 61(7), 4060–4079. https://doi.org/10.1109/TIT.2015.2429632
Bajwa, W. U., M. F. Duarte, and R. Calderbank. “Conditioning of Random Block Subdictionaries With Applications to Block-Sparse Recovery and Regression.” IEEE Transactions on Information Theory 61, no. 7 (July 1, 2015): 4060–79. https://doi.org/10.1109/TIT.2015.2429632.
Bajwa WU, Duarte MF, Calderbank R. Conditioning of Random Block Subdictionaries With Applications to Block-Sparse Recovery and Regression. IEEE Transactions on Information Theory. 2015 Jul 1;61(7):4060–79.
Bajwa, W. U., et al. “Conditioning of Random Block Subdictionaries With Applications to Block-Sparse Recovery and Regression.” IEEE Transactions on Information Theory, vol. 61, no. 7, July 2015, pp. 4060–79. Scopus, doi:10.1109/TIT.2015.2429632.
Bajwa WU, Duarte MF, Calderbank R. Conditioning of Random Block Subdictionaries With Applications to Block-Sparse Recovery and Regression. IEEE Transactions on Information Theory. 2015 Jul 1;61(7):4060–4079.

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

July 1, 2015

Volume

61

Issue

7

Start / End Page

4060 / 4079

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing