Limits on Sparse Data Acquisition: RIC Analysis of Finite Gaussian Matrices
arXiv:1802.03195 · doi:10.1109/TIT.2018.2859327
Abstract
One of the key issues in the acquisition of sparse data by means of compressed sensing (CS) is the design of the measurement matrix. Gaussian matrices have been proven to be information-theoretically optimal in terms of minimizing the required number of measurements for sparse recovery. In this paper we provide a new approach for the analysis of the restricted isometry constant (RIC) of finite dimensional Gaussian measurement matrices. The proposed method relies on the exact distributions of the extreme eigenvalues for Wishart matrices. First, we derive the probability that the restricted isometry property is satisfied for a given sufficient recovery condition on the RIC, and propose a probabilistic framework to study both the symmetric and asymmetric RICs. Then, we analyze the recovery of compressible signals in noise through the statistical characterization of stability and robustness. The presented framework determines limits on various sparse recovery algorithms for finite size problems. In particular, it provides a tight lower bound on the maximum sparsity order of the acquired data allowing signal recovery with a given target probability. Also, we derive simple approximations for the RICs based on the Tracy-Widom distribution.
arXiv comment11 pages, 6 figures, accepted for publication in IEEE transactions on information theory
References in corpus (15)
- Level-Spacing Distributions and the Airy Kernel
- Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
- From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals
- Shape Fluctuations and Random Matrices
- The Convex Geometry of Linear Inverse Problems
- Compressive estimation of doubly selective channels in multicarrier systems: Leakage effects and sparsity-enhancing processing
- Universality in polytope phase transitions and message passing algorithms
- On the Numerical Evaluation of Distributions in Random Matrix Theory: A Review
- Accuracy of the Tracy--Widom limits for the extreme eigenvalues in white Wishart matrices
- The right tail exponent of the Tracy-Widom-beta distribution
- On the probability that all eigenvalues of Gaussian, Wishart, and double Wishart random matrices lie within an interval
- Operational Rate-Distortion Performance of Single-source and Distributed Compressed Sensing
- PDEs satisfied by extreme eigenvalues distributions of GUE and LUE
- Graded quantization for multiple description coding of compressive measurements
- D-OAMP: A Denoising-based Signal Recovery Algorithm for Compressed Sensing