Message-Passing De-Quantization With Applications to Compressed Sensing

• Published in: IEEE transactions on signal processing 2012-12, Vol.60 (12), p.6270-6281
• Main Authors: Kamilov, U. S., Goyal, V. K., Rangan, S.
• Format: Article
• Language: English
• Subjects: AC-DC converters; Algorithms; Analog-digital conversion, digital-analog conversion, pcm coding; Analog-to-digital conversion; Applied sciences; approximate message passing; Approximation algorithms; belief propagation; Coding, codes; Compressed sensing; Detection, estimation, filtering, equalization, prediction; Estimation; Exact sciences and technology; frames; Information, signal and communications theory; Linear systems; non-regular quantizers; overcomplete representations; Quantization; Sampling, quantization; Signal and communications theory; Signal, noise; Slepian-Wolf coding; Sparsity; Studies; Telecommunications and information theory; Transforms; Wyner-Ziv coding
• ISSN: 1053-587X; 1941-0476
• DOI: 10.1109/TSP.2012.2217334

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.