PaperlayerView exact revision on arXiv

Source-linked AI summary

Message-Passing Estimation from Quantized Samples

Ulugbek Kamilov, Vivek K. Goyal, Sundeep Rangan

arXiv:1105.6368v2cs.ITmath.ITmath.STstat.TH

TL;DR

Quantized linear measurements couple signal components and make simple linear reconstruction suboptimal. This paper applies GAMP with general priors and scalar quantizers, reporting improved reconstruction and rate-distortion performance and using state evolution to predict performance for large random transforms.

  • Problem

    Quantization is nonlinear and mixes with the linear transform, making estimation from quantized measurements a joint reconstruction problem.

    Source: §I · p. 1

  • Method

    The paper uses GAMP with general priors and quantizers, and applies state evolution to predict performance and optimize quantizers for reconstruction distortion.

    Source: §IX · pp. 10–11

  • Results

    Experiments show significant gains over traditional reconstruction schemes, and uniform modulo quantization achieves the best rate–distortion performance among the compared quantizers.

    Source: A. Overcomplete Expansions · p. 9, §IX · p. 11

  • Takeaways & Limitations

    GAMP provides a tractable and efficient method for high-dimensional estimation with non-regular scalar quantization, across overcomplete and undercomplete settings.

    Source: §IX · pp. 10–11

Abstract

from arXiv · show

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 generalized approximate message passing (GAMP) 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. GAMP is a recently-developed class of algorithms that uses Gaussian approximations in belief propagation and allows arbitrary separable input and output channels. 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. Non-regular quantization is empirically demonstrated to greatly improve rate-distortion performance in some problems with oversampling or with undersampling combined with a sparsity-inducing prior. Under the assumption of a Gaussian measurement matrix with i.i.d. entries, the asymptotic error performance of GAMP can be accurately predicted and tracked through the state evolution formalism. We additionally use state evolution to design MSE-optimal scalar quantizers for GAMP signal reconstruction and empirically demonstrate the superior error performance of the resulting quantizers.

I. INTRODUCTION

The paper addresses joint estimation from quantized, linearly mixed measurements, where quantization is nonlinear and the transform couples signal components. It presents GAMP for broad priors and quantizers, with state evolution for performance prediction and quantizer design.

I. INTRODUCTION

  • Quantized linear measurements require joint estimation because quantization is nonlinear and the transform mixes signal components.The paper notes that nonlinear reconstruction can improve on linear estimation for quantized transformed data.Source: §I · p. 1
  • GAMP extends Gaussian-approximated belief propagation to nonlinear output channels, avoiding heuristic additive-noise models while keeping computation low.Conventional BP for continuous-valued quantities requires density discretization, which is inexact and computationally expensive.Source: §I · p. 1

A. Contributions

  • GAMP supports essentially arbitrary quantizers, including non-regular quantizers whose cells can be unions of disjoint intervals.The paper identifies non-regular modulo quantization as a tractable way to exploit such quantizers in high-dimensional estimation.Source: A. Contributions · pp. 1–2
  • GAMP accommodates independent-component priors that may induce sparsity, and state evolution characterizes componentwise performance for certain large random transforms.The state-evolution analysis can evaluate componentwise metrics such as MSE.Source: A. Contributions · p. 2
  • Simulations report improved performance over traditional methods, while certain large random sparse transforms admit conditions under which GAMP reconstruction is provably optimal.The algorithm is reported to work well in roughly 10 to 20 iterations, with matrix multiplications by A and A^T as the dominant per-iteration cost.Source: A. Contributions · p. 2
  • State evolution is used to optimize quantizers for the asymptotic reconstruction distortion of GAMP, rather than only the quantizer input-output MSE.The paper notes that using random A supports the rigor of the state-evolution formalism; GAMP’s effectiveness does not depend on random A.Source: A. Contributions · p. 2

B. Outline

  • The paper proceeds from background and problem geometry to the Bayesian formulation, GAMP, state evolution, quantizer optimization, and experiments.The outline places the conclusions after the experimental results.Source: B. Outline · p. 2

C. Notation

The paper establishes notation and scalar-quantization concepts used in its estimation framework. It distinguishes regular from non-regular quantizers and describes when non-regular quantization is useful.

C. Notation

  • Boldface denotes vectors and matrices, while normal weight denotes scalars; the paper also specifies its density and Gaussian notation.The same lowercase density notation is used for scalar densities when they are separable and identical across components.Source: C. Notation · p. 2

A. Scalar Quantization

  • A scalar quantizer maps real inputs through an encoder and decoder, with decision thresholds defining its quantization cells.The encoder maps to an index set and the decoder maps indices to reproduction points.Source: A. Scalar Quantization · p. 2
  • Regular quantizers have single-interval cells, whereas non-regular quantizers can map multiple disjoint intervals to an output cell.A non-regular quantizer’s encoder can be represented as a regular quantizer followed by a many-to-one binning function.Source: A. Scalar Quantization · pp. 2–3
  • Non-regular quantizers can help when side information aids recovery, as in Wyner–Ziv and multiple-description coding,.In these settings, the rate can scale with K while recovered resolution scales with K′, where K′ > K.Source: A. Scalar Quantization · p. 3
  • Lloyd’s algorithm optimizes a quantizer iteratively by updating decision boundaries and output levels.At fixed rate, conventional scalar-quantizer MSE optimization need only consider regular quantizers; non-regular quantizers are not strictly better for that objective.Source: A. Scalar Quantization · p. 3

B. Compressed Sensing

Compressed sensing estimates sparse or approximately sparse signals from fewer linear measurements than signal dimensions. This paper focuses on the additional degradation caused by quantization and on reconstruction methods that use quantizer-cell information.

B. Compressed Sensing

  • Compressed sensing estimates sparse or approximately sparse signals from m < n scalar linear measurements, potentially with additive noise.The measurement matrix A is assumed available to the estimator.Source: B. Compressed Sensing · p. 3
  • The paper assumes x itself is sparse or approximately sparse and focuses on measurement degradation from quantization, not the noiseless model.The sparse representation is not required to be expressed in a separate transform domain.Source: B. Compressed Sensing · p. 3
  • The lasso trades off data fidelity against solution sparsity through its parameter γ.The estimator is presented as a commonly studied approach for the noisy linear measurement model.Source: B. Compressed Sensing · p. 3
  • For quantized measurements, prior work reports gains from using quantizer partition cells in the reconstruction constraint, while generic convex solvers can be costly.The paper uses a low-complexity generalization of earlier approximate belief-propagation methods to handle quantization effects precisely.Source: B. Compressed Sensing · p. 3

C. Belief Propagation

Belief propagation estimates signal components by iteratively passing messages rather than directly marginalizing a high-dimensional posterior. The paper applies Gaussian approximations to quantized linear measurements and considers both overcomplete and undercomplete expansions.

C. Belief Propagation

  • Belief propagation replaces direct posterior marginalization with iterative messages on a factor graph.The model assumes an i.i.d. signal prior and a separable, identical measurement channel across entries.Source: C. Belief Propagation · pp. 3–4
  • Dense measurement matrices make direct BP impractical because measurement updates require high-dimensional integration and discrete quadrature.BP can be MSE-optimal under verifiable conditions when the corresponding state evolution has a unique fixed point.Source: C. Belief Propagation · p. 4
  • Gaussian approximations simplify BP, and for certain large random matrices state evolution can accurately predict relaxed-BP and AMP error performance.The paper uses generalized approximate message passing for its quantized-measurement setting.Source: C. Belief Propagation · p. 4, §III · p. 4

III. QUANTIZED LINEAR EXPANSIONS

  • The quantized linear model is y = Q(Ax), with x in R^n, A in R^(m×n), and scalar quantization applied to the m mixed measurements.The paper evaluates per-component MSE and considers both m ≥ n and m < n.Source: §III · p. 4

A. Overcomplete Expansions

Overcomplete measurements constrain the signal through intersecting quantizer-consistent sets, while nonlinear reconstruction can outperform linear methods. Oversampling may improve estimation but can be inefficient in raw bit rate, motivating non-regular quantization.

A. Overcomplete Expansions

  • Linear reconstruction can be far from optimal even when its additive-noise model is accurate.For uniform tight frames and deterministic signals, linear reconstruction has MSE inversely proportional to the number of measurements under the stated model.Source: A. Overcomplete Expansions · p. 4
  • Intersecting n regular single-sample consistent sets forms a parallelotope, and adding more measurements refines the partition.For the illustrated two-dimensional signal, two measurements give a bounded convex cell and a third further partitions it.Source: A. Overcomplete Expansions · p. 4, Figure 1 · p. 5
  • With an oversampled Fourier transform and uniform quantization, consistent estimates achieve O(m^-2) MSE under a mild signal-norm assumption.Alternating projections and linear programming can find consistent estimates, but their computational complexity is high and their corner-of-set solutions are suboptimal.Source: A. Overcomplete Expansions · pp. 4–5
  • High oversampling can trade MSE against power or manufacturing cost, but raw bit rate yields Θ(R^-2) MSE, poorer than the exponential decrease for Nyquist-rate scalar quantization.The paper explores non-regular quantization as an alternative to recoding the raw output.Source: A. Overcomplete Expansions · p. 5

B. Non-Regular Quantization

Non-regular quantization bins multiple slabs into one output, reducing quantization rate but introducing ambiguity. When multiple measurements disambiguate the slabs, binning can reduce rate without increasing distortion, though estimation is more complex.

B. Non-Regular Quantization

  • Binning leaves single-sample boundaries unchanged but makes consistent sets unions of slabs that may be disconnected, creating ambiguity that can increase distortion.Taking more than n quantized samples may provide enough information to disambiguate the slabs.Source: B. Non-Regular Quantization · p. 5
  • When samples disambiguate the slabs, binning reduces rate without increasing distortion, at the cost of estimation complexity.The paper presents a tractable and effective reconstruction method for non-regular quantizers, described as the first such method to the authors’ knowledge.Source: B. Non-Regular Quantization · pp. 5–6
  • The earlier proposed reconstruction for binned quantization searches combinations of binning-function values, with complexity exponential in m.The cited bounds on reconstruction error do not address reconstruction algorithms.Source: B. Non-Regular Quantization · pp. 5–6
  • A single binned sample can yield a disconnected consistent set, and two samples can leave four convex cells; a third may reduce these to one convex set.This is the illustrated progression for non-regular quantization in a two-dimensional signal space.Source: B. Non-Regular Quantization · p. 5, Figure 2 · p. 6

C. Undercomplete Expansions

Undercomplete measurements cannot uniquely recover an unrestricted vector, but sparsity can help identify its support and enable estimation. Non-regular quantization can still disambiguate sparse supports, although a naive reconstruction search is combinatorial.

C. Undercomplete Expansions

  • Because A is many-to-one when its rank is below n, even unquantized measurements leave a subspace of possible signals; sparsity can support accurate estimation from quantized measurements.For a matrix in general position, the subspace has dimension n − m before quantization.Source: C. Undercomplete Expansions · p. 6
  • For a k-sparse signal with known support and a full-rank submatrix, quantized undercomplete measurements form an overcomplete expansion of the supported signal components.The overcomplete-estimation discussion therefore applies when the support is known.Source: C. Undercomplete Expansions · p. 6
  • Two measurements usually identify the support in the illustrated sparse setting, and non-regular quantization can also uniquely determine it in some cases.For fixed scalar quantizers, ambiguity becomes less likely as k decreases or n, m, or the signal norm increases.Source: C. Undercomplete Expansions · pp. 6–7
  • The naive approach searches combinatorially over both supports and bin combinations, while the paper provides a tractable and effective reconstruction method.The paper characterizes the naive search as extremely complex.Source: C. Undercomplete Expansions · pp. 6–7

IV. ESTIMATION FROM QUANTIZED SAMPLES: BAYESIAN FORMULATION

The Bayesian formulation estimates an i.i.d. random vector from scalar-quantized linear measurements by minimizing mean-squared error. It specifies the random measurement and noise model and uses GAMP with componentwise estimation functions.

IV. ESTIMATION FROM QUANTIZED SAMPLES: BAYESIAN FORMULATION

  • The formulation models x with i.i.d. prior entries, A with i.i.d. Gaussian entries of variance 1/m, and pre-quantization noise with i.i.d. Gaussian entries of variance σ².The quantizer is scalar, with identical component quantizers having K output levels.Source: §IV · p. 7
  • The estimator depends on A, y, Q, and σ², and the objective is to minimize n^-1 E[||x − x̂||²].The primary interest is the zero-noise case, while allowing nonzero noise clarifies the derivations.Source: §IV · p. 7

A QUANTIZER OUTPUT CHANNEL

  • Each quantized measurement indicates that its pre-quantization value lies in the inverse image of the observed quantizer output.This makes the quantized measurement a separable output channel for GAMP.Source: A QUANTIZER OUTPUT CHANNEL · p. 7
  • GAMP produces successive signal estimates using its input and output estimation functions at each iteration.The algorithm is described as approximating belief-propagation updates with scalar parameters and first-order approximations.Source: A QUANTIZER OUTPUT CHANNEL · p. 7
  • In the algorithm’s notation, A² is the elementwise square of A, and the estimation functions are applied componentwise.This distinguishes the matrix operation from a matrix product.Source: A QUANTIZER OUTPUT CHANNEL · pp. 7–8
  • The algorithm distinguishes variable updates from measurement updates and initializes variable estimates using the prior mean and variance.The updates are indexed by variable and measurement nodes, respectively.Source: A QUANTIZER OUTPUT CHANNEL · p. 8
  • The input functions F_in and E_in are conditional mean and variance for a prior variable observed in Gaussian noise.They are applied component by component and can be evaluated numerically for given inputs and variance.Source: A QUANTIZER OUTPUT CHANNEL · p. 8
  • The output functions F_out and E_out are conditional mean and variance for a Gaussian variable given the quantized observation.The supplied passage says these functions have closed-form expressions involving erf.Source: A QUANTIZER OUTPUT CHANNEL · p. 8

VI. STATE EVOLUTION FOR GAMP

State evolution (SE) characterizes GAMP’s asymptotic behavior for large random measurement matrices, with the asymptotic MSE given by its recursion. This provides a way to analyze GAMP even with non-Gaussian priors and nonlinear quantizers.

Asymptotic characterization

  • For large i.i.d. Gaussian measurement matrices, the estimate’s componentwise behavior converges to a scalar model described by SE, and its asymptotic MSE is τ̄_t.The result holds as m,n grow with n/m tending to a fixed ratio, under further technical conditions.Source: §VI · p. 8
  • SE can serve as a quantizer-design metric because its recursion predicts asymptotic MSE.Other, non-squared-error distortions may also be considered.Source: §VI · p. 8
  • For certain large sparse random matrices, a unique SE fixed point implies that GAMP is asymptotically mean-square optimal.The recursion decreases monotonically to its largest fixed point.Source: §VI · p. 8
  • SE precisely characterizes GAMP’s asymptotic behavior for large random transforms despite a non-Gaussian prior and nonlinear quantization.The recursion can also evaluate componentwise performance metrics other than MSE.Source: §VI · p. 8

VII. QUANTIZER OPTIMIZATION

The paper optimizes quantizers for reconstruction MSE rather than quantization error alone. State evolution makes this optimization tractable by evaluating GAMP’s asymptotic MSE for candidate quantizers.

Quantizer design objective

  • Conventional quantizer design minimizes measurement quantization error, whereas this setting targets the reconstruction MSE of the estimated vector.The paper frames the objective as n^-1 E[||x − x̂||^2], rather than m^-1 E[||z − Q(z)||^2].Source: §VII · p. 8

SE-based optimization

  • Modeling the quantizer as part of the channel lets SE recast quantizer design as minimizing GAMP’s asymptotic MSE.The stated optimization is over all K-level regular scalar quantizers.Source: §VII · p. 8
  • The optimization uses the limiting recursion as t → ∞, while simulations show close to limiting performance after relatively few iterations.Finite-iteration optimization is also possible.Source: §VII · pp. 8–9
  • SE remains practical for quantizer optimization because it evaluates quickly and changes only slightly when quantizer boundaries change slightly.Finite differences approximate derivatives when closed-form derivatives are difficult to obtain.Source: §VII · p. 9

VIII. EXPERIMENTAL RESULTS

Across the oversampled and compressive-sensing experiments, GAMP outperforms the compared reconstruction methods. The results also favor non-regular quantizers over the tested alternatives for rate–distortion performance.

A. Overcomplete Expansions

  • More than 5 dB improvement over both LMMSE and MAP is reported for many oversampling ratios, with GAMP also computationally simpler than MAP’s quadratic program.Figure 5 compares median squared error across oversampling ratios for a 16-level regular uniform quantizer and 200 Monte Carlo trials.Source: A. Overcomplete Expansions · p. 9, Figure 5 · p. 9
  • The uniform modulo quantizer achieves the best rate–distortion performance, while the Lloyd-designed quantizer performs comparatively poorly.The Lloyd design minimizes quantizer input-output MSE rather than accounting for the nonlinear estimator that follows.Source: A. Overcomplete Expansions · p. 9, Figure 6 · p. 9

B. Compressive Sensing with Quantized Measurements

IX. CONCLUSIONS

GAMP is an effective, efficient approach to quantized linear estimation that supports essentially arbitrary priors and quantization functions. Experiments show improvements over traditional reconstruction schemes, while the authors caution against interpreting the results as a case for quantized linear expansions as compression.

IX. CONCLUSIONS

  • GAMP supports essentially arbitrary priors and quantization functions, including non-regular scalar quantization in high-dimensional estimation.The formulation uses an i.i.d. prior and permits either more or fewer measurements than signal dimensions, with or without sparsity-inducing priors.Source: §IX · pp. 10–11
  • For large random transforms, GAMP is computationally simple and its performance admits precise characterization through state evolution.The conclusion also notes that extensions such as hybrid approximate message passing may in the future address signals described by general graphical models.Source: §IX · p. 11
  • Experiments show significant performance improvement over traditional reconstruction schemes, but the authors do not advocate quantized linear expansions as a compression technique.The caution applies to both oversampled and undersampled sparse cases; comparison to rate-distortion bounds would obscure the contribution.Source: §IX · p. 11

Related papers

Loading 1105.6368v2…