Information-Theoretic Bounds for Adaptive Sparse Recovery
We derive an information-theoretic lower bound for sample complexity in sparse recovery problems where inputs can be chosen sequentially and adaptively. This lower bound is in terms of a simple mutual information expression and unifies many different linear and nonlinear observation models. Using this formula we derive bounds for adaptive compressive sensing (CS), group testing and 1-bit CS problems. We show that adaptivity cannot decrease sample complexity in group testing, 1-bit CS and CS with linear sparsity. In contrast, we show there might be mild performance gains for CS in the sublinear regime. Our unified analysis also allows characterization of gains due to adaptivity from a wider perspective on sparse problems.
Code (0)
등록된 구현이 없습니다.
Tasks
Compressive SensingSimilar Papers 제목 키워드 기반
Sparse Recovery with Linear and Nonlinear Observations: Dependent and Noisy Data
We formulate sparse support recovery as a salient set identification problem and use information-theoretic analyses to characterize the recovery performance and sample complexity. We consider a very general model where w…
regressionSupport Recovery in the Phase Retrieval Model: Information-Theoretic Fundamental Limits
The support recovery problem consists of determining a sparse subset of variables that is relevant in generating a set of observations. In this paper, we study the support recovery problem in the phase retrieval model co…
RetrievalPartial Recovery Bounds for the Sparse Stochastic Block Model
In this paper, we study the information-theoretic limits of community detection in the symmetric two-community stochastic block model, with intra-community and inter-community edge probabilities $\frac{a}{n}$ and $\frac{…
Community DetectionStochastic Block ModelThe Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Information
The rising footprint of machine learning has led to a focus on imposing \emph{model sparsity} as a means of reducing computational and memory costs. For deep neural networks (DNNs), the state-of-the-art accuracy-vs-spars…
Limits on Support Recovery with Probabilistic Models: An Information-Theoretic Framework
The support recovery problem consists of determining a sparse subset of a set of variables that is relevant in generating a set of observations, and arises in a diverse range of settings such as compressive sensing, and …
Compressive Sensing