Message-passing de-quantization with applications to compressed sensing

Ulugbek S. Kamilov, Vivek K. Goyal, Sundeep Rangan

Research output: Contribution to journalArticlepeer-review


Estimation of a vector from quantized linear measurements is a common problem for which simple linear techniques are suboptimalsometimes 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.

Original languageEnglish (US)
Article number6295675
Pages (from-to)6270-6281
Number of pages12
JournalIEEE Transactions on Signal Processing
Issue number12
StatePublished - 2012


  • Analog-to-digital conversion
  • Slepian-Wolf coding
  • Wyner-Ziv coding
  • approximate message passing
  • belief propagation
  • compressed sensing
  • frames
  • non-regular quantizers
  • overcomplete representations
  • quantization

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'Message-passing de-quantization with applications to compressed sensing'. Together they form a unique fingerprint.

Cite this