Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement Matrices

DOI10.1109/TIT.2010.2046199zbMATH Open1366.94130arXiv0806.0604MaRDI QIDQ5281472FDOQ5281472

Authors: Wei Wang, Martin J. Wainwright, Kannan Ramchandran 

Publication date: 27 July 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We study the information-theoretic limits of exactly recovering the support of a sparse signal using noisy projections defined by various classes of measurement matrices. Our analysis is high-dimensional in nature, in which the number of observations $n$, the ambient signal dimension $p$, and the signal sparsity $k$ are all allowed to tend to infinity in a general manner. This paper makes two novel contributions. First, we provide sharper necessary conditions for exact support recovery using general (non-Gaussian) dense measurement matrices. Combined with previously known sufficient conditions, this result yields sharp characterizations of when the optimal decoder can recover a signal for various scalings of the sparsity $k$ and sample size $n$, including the important special case of linear sparsity ($k=Theta(p)$) using a linear scaling of observations ($n=Theta(p)$). Our second contribution is to prove necessary conditions on the number of observations $n$ required for asymptotically reliable recovery using a class of $gamma$-sparsified measurement matrices, where the measurement sparsity $gamma(n,p,k)in(0,1]$ corresponds to the fraction of non-zero entries per row. Our analysis allows general scaling of the quadruplet $(n,p,k,gamma)$, and reveals three different regimes, corresponding to whether measurement sparsity has no effect, a minor effect, or a dramatic effect on the information-theoretic limits of the subset recovery problem.

Full work available at URL: https://arxiv.org/abs/0806.0604

Recommendations

• Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting
• An Information-Theoretic Study for Joint Sparsity Pattern Recovery With Different Sensing Matrices
• Approximate Sparsity Pattern Recovery: Information-Theoretic Lower Bounds
• Note on sparsity in signal recovery and in matrix identification
• Sparse signal recovery using a new class of random matrices
• An evaluation of the sparsity degree for sparse recovery with deterministic measurement matrices
• Information Theoretic Bounds for Compressed Sensing
• On the Recovery Limit of Sparse Signals Using Orthogonal Matching Pursuit
• Limits on Support Recovery of Sparse Signals via Multiple-Access Communication Techniques
• A simple Gaussian measurement bound for exact recovery of block-sparse signals

Mathematics Subject Classification ID

Inference from stochastic processes and prediction (62M20) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (probabilistic aspects) (60B20) Information theory (general) (94A15) Measures of information, entropy (94A17)

Cited In (18)

• Sparse regression: scalable algorithms and empirical performance
• Sharp support recovery from noisy random measurements by \(\ell_1\)-minimization
• Sparse classification: a scalable discrete optimization perspective
• A note on the asymptotic distribution of lasso estimator for correlated data
• Compressive sampling and rapid reconstruction of broadband frequency hopping signals with interference
• Which bridge estimator is the best for variable selection?
• Sparse high-dimensional linear regression. Estimating squared error and a phase transition
• A novel probabilistic approach for vehicle position prediction in free, partial, and full GPS outages
• Sparse sensor placement optimization for classification
• Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting
• On the Fundamental Limits of Recovering Tree Sparse Vectors From Noisy Linear Measurements
• Measurement Bounds for Sparse Signal Ensembles via Graphical Models
• Compressive classification: where wireless communications meets machine learning
• Note on sparsity in signal recovery and in matrix identification
• Feature selection for data integration with mixed multiview data
• The all-or-nothing phenomenon in sparse linear regression
• An Information-Theoretic Study for Joint Sparsity Pattern Recovery With Different Sensing Matrices
• Iterative algorithm for discrete structure recovery

This page was built for publication: Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5281472)