Conditioning of Random Block Subdictionaries with Applications to Block-Sparse Recovery and Regression
arXiv:1309.5310 · doi:10.1109/TIT.2015.2429632
Abstract
The linear model, in which a set of observations is assumed to be given by a linear combination of columns of a matrix, 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 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 subdictionaries are well conditioned. This result is fundamentally different from prior work on block-sparse inference because (i) it provides conditions that can be explicitly computed in polynomial time, (ii) 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 (iii) it suggests that the spectral norm and the quadratic-mean block coherence of the dictionary (rather than the worst-case coherences) fundamentally limit the scaling of dimensions of the well-conditioned block subdictionaries. Second, this paper investigates the problems of block-sparse recovery and block-sparse regression in underdetermined settings. Near-optimal block-sparse recovery and regression are possible for certain 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.
arXiv comment39 pages, 3 figures. A revised and expanded version of the paper published in IEEE Transactions on Information Theory (DOI: 10.1109/TIT.2015.2429632); this revision includes corrections in the proofs of some of the results
References in corpus (18)
- Simultaneous analysis of Lasso and Dantzig selector
- Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
- Model-Based Compressive Sensing
- Structured Compressed Sensing: From Theory to Applications
- High-Resolution Radar via Compressed Sensing
- Recovering low-rank matrices from few coefficients in any basis
- Support union recovery in high-dimensional multivariate regression
- Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors
- Near-ideal model selection by minimization
- Subspace Methods for Joint Sparse Recovery
- Certifying the restricted isometry property is hard
- Block-Sparse Recovery via Convex Optimization
- Causal Network Inference via Group Sparse Regularization
- Two are better than one: Fundamental parameters of frame coherence
- Near-Oracle Performance of Greedy Block-Sparse Estimation Techniques from Noisy Measurements
- Sparse Recovery from Combined Fusion Frame Measurements
- Uncertainty Relations and Sparse Signal Recovery for Pairs of General Signal Sets
- Measurement Bounds for Sparse Signal Ensembles via Graphical Models