Subsampling at Information Theoretically Optimal Rates
arXiv:1202.2525
Abstract
We study the problem of sampling a random signal with sparse support in frequency domain. Shannon famously considered a scheme that instantaneously samples the signal at equispaced times. He proved that the signal can be reconstructed as long as the sampling rate exceeds twice the bandwidth (Nyquist rate). Candès, Romberg, Tao introduced a scheme that acquires instantaneous samples of the signal at random times. They proved that the signal can be uniquely and efficiently reconstructed, provided the sampling rate exceeds the frequency support of the signal, times logarithmic factors. In this paper we consider a probabilistic model for the signal, and a sampling scheme inspired by the idea of spatial coupling in coding theory. Namely, we propose to acquire non-instantaneous samples at random times. Mathematically, this is implemented by acquiring a small random subset of Gabor coefficients. We show empirically that this scheme achieves correct reconstruction as soon as the sampling rate exceeds the frequency support of the signal, thus reaching the information theoretic limit.
arXiv comment5 pages, 4 figures, minor corrections
References in corpus (5)
- Message Passing Algorithms for Compressed Sensing
- On Phase Transition of Compressed Sensing in the Complex Domain
- The Effect of Spatial Coupling on Compressive Sensing
- Spatially Coupled Ensembles Universally Achieve Capacity under Belief Propagation
- Asymptotic Analysis of Complex LASSO via Complex Approximate Message Passing (CAMP)