Message-Passing De-Quantization With Applications to Compressed Sensing
- 7 September 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 60 (12) , 6270-6281
Abstract
Estimation of a vector from quantized linear measurements is a common problem for which simple linear techniques are suboptimal-sometimes greatly so. This paper develops message-passing de-quantization (MPDQ) algorithms for minimum mean-squared error estimation of a random vector from quantized linear measurements, notably allowing the linear expansion to be overcomplete or undercomplete and the scalar quantization to be regular or non-regular. The algorithm is based on generalized approximate message passing (GAMP), a recently-developed Gaussian approximation of loopy belief propagation for estimation with linear transforms and nonlinear componentwise-separable output channels. For MPDQ, scalar quantization of measurements is incorporated into the output channel formalism, leading to the first tractable and effective method for high-dimensional estimation problems involving non-regular scalar quantization. The algorithm is computationally simple and can incorporate arbitrary separable priors on the input vector including sparsity-inducing priors that arise in the context of compressed sensing. Moreover, under the assumption of a Gaussian measurement matrix with i.i.d. entries, the asymptotic error performance of MPDQ can be accurately predicted and tracked through a simple set of scalar state evolution equations. We additionally use state evolution to design MSE-optimal scalar quantizers for MPDQ signal reconstruction and empirically demonstrate the superior error performance of the resulting quantizers. In particular, our results show that non-regular quantization can greatly improve rate-distortion performance in some problems with oversampling or with undersampling combined with a sparsity-inducing prior.Keywords
All Related Versions
This publication has 51 references indexed in Scilit:
- Subspace Pursuit for Compressive Sensing Signal ReconstructionIEEE Transactions on Information Theory, 2009
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- Compressive Sampling and Lossy CompressionIEEE Signal Processing Magazine, 2008
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?IEEE Transactions on Information Theory, 2006
- Compressed sensingIEEE Transactions on Information Theory, 2006
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency informationIEEE Transactions on Information Theory, 2006
- Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition2002
- Adaptive time-frequency decompositionsOptical Engineering, 1994
- Matching pursuits with time-frequency dictionariesIEEE Transactions on Signal Processing, 1993
- Orthogonal least squares methods and their application to non-linear system identificationInternational Journal of Control, 1989