PaperlayerView exact revision on arXiv

Source-linked AI summary

Dequantizing Compressed Sensing: When Oversampling and Non-Gaussian Constraints Combine

Laurent Jacques, David K. Hammond, M. Jalal Fadili

arXiv:0902.2367v4math.OCcs.IT

TL;DR

The paper addresses recovery of sparse or compressible signals from uniformly quantized measurements, where quantization distortion is not well modeled as Gaussian noise. It introduces BPDQ_p decoders with ℓp fidelity constraints and shows that, for Gaussian sensing matrices in oversampled settings, they reduce quantization-induced reconstruction error relative to BPDN by √(p + 1).

  • Problem

    Recovering sparse or compressible signals from uniformly quantized measurements requires a reconstruction model that represents quantization distortion more faithfully than BPDN.

  • Method

    BPDQ_p minimizes signal sparsity in ℓ1 subject to an ℓp-norm residual constraint for 2 ≤ p ≤ ∞, with stability analyzed through an extended ℓp Restricted Isometry Property.

  • Results

    For Gaussian random matrices and uniformly quantized measurements, BPDQ_p reduces quantization-induced reconstruction error relative to BPDN = BPDQ_2 by √(p + 1) with high probability when measurements grow sufficiently with p.

  • Takeaways & Limitations

    BPDQ_p provides substantial reconstruction-error reduction in oversampled settings, supported by theoretical analysis and experiments on one-dimensional signals and an image.

Abstract

from arXiv · show

In this paper we study the problem of recovering sparse or compressible signals from uniformly quantized measurements. We present a new class of convex optimization programs, or decoders, coined Basis Pursuit DeQuantizer of moment $p$ (BPDQ$_p$), that model the quantization distortion more faithfully than the commonly used Basis Pursuit DeNoise (BPDN) program. Our decoders proceed by minimizing the sparsity of the signal to be reconstructed subject to a data-fidelity constraint expressed in the $\ell_p$-norm of the residual error for $2\leq p\leq \infty$. We show theoretically that, (i) the reconstruction error of these new decoders is bounded if the sensing matrix satisfies an extended Restricted Isometry Property involving the $\ell_p$ norm, and (ii), for Gaussian random matrices and uniformly quantized measurements, BPDQ$_p$ performance exceeds that of BPDN by dividing the reconstruction error due to quantization by $\sqrt{p+1}$. This last effect happens with high probability when the number of measurements exceeds a value growing with $p$, i.e. in an oversampled situation compared to what is commonly required by BPDN = BPDQ$_2$. To demonstrate the theoretical power of BPDQ$_p$, we report numerical simulations on signal and image reconstruction problems.

I. INTRODUCTION

The paper introduces BPDQ_p, convex sparse-recovery decoders whose ℓp fidelity constraint models bounded, non-Gaussian quantization distortion. For Gaussian sensing matrices, oversampling can reduce quantization-induced reconstruction error relative to BPDN.

  • Quantization error is essentially uniform and bounded, making Gaussian-noise modeling theoretically unsatisfactory for compressed sensing.
  • BPDQ_p minimizes the reconstructed signal’s ℓ1 sparsity subject to a bounded ℓp residual constraint for 2 ≤ p ≤ ∞.As p approaches infinity, the fidelity term reproduces the quantization-consistency constraint.
  • The paper studies which moment p provides the best reconstruction as sparsity and measurement count vary, rather than assuming p = ∞ is optimal.
  • For a fixed sparsity level, when measurements exceed a p-dependent minimum, BPDQ_p reduces quantization-induced reconstruction error relative to BPDN = BPDQ_2 by √(p + 1).This improvement occurs in oversampled situations and does not favor p = ∞ overall.
  • When measurement bit-depth is fixed by hardware, gathering more measurements is presented as the practical route to improve reconstruction quality.The paper motivates oversampling for fixed-bit-depth sensors and validates BPDQ_p on one-dimensional signals and an image.
  • The theoretical guarantees use an extended ℓp Restricted Isometry Property, which Gaussian random matrices satisfy with high probability given sufficiently many measurements.

II. COMPRESSED SENSING AND QUANTIZATION OF MEASUREMENTS

The section formulates compressed sensing with uniformly quantized measurements and explains why standard BPDN inadequately models quantization distortion. It introduces the extended RIP framework used to analyze stability under nonstandard residual norms.

  • Measurement model: Compressed sensing acquires sparse or compressible signals through m linear measurements, typically with sparsity K satisfying K ≤ m ≤ N.The signal is represented in a canonical or orthogonal basis, and the measurements are produced by a sensing matrix.
  • Measurement model: Uniform quantization maps each measurement into a bin of width α, producing a quantized vector and distortion n.The model treats quantization as the dominant distortion source and excludes saturation and non-uniform quantization.
  • Model scope: The section restricts the quantization model to unsaturated uniform quantization, leaving non-uniform quantization for future research.Saturation occurs when measurements exceed the quantizer’s operating range determined by available bit depth.
  • RIP framework: BPDN stability follows from the conventional RIP2,2, which is the p = q = 2 instance of the extended RIPp,q.The extended property applies norm-based embeddings to sparse signals and supports analysis beyond the standard Euclidean setting.
  • RIP framework: For sub-Gaussian random matrices, RIP2,2 holds with overwhelming probability when m ≥ cK log(N/K), for a constant c independent of the dimensions.Standard Gaussian and Bernoulli constructions are examples of matrices satisfying this property.
  • Limitations of BPDN: BPDN handles quantization by constraining the residual in ℓ2, but its solution need not satisfy quantization consistency.This may discard information about the structured, uniformly distributed nature of quantization noise.

III. BASIS PURSUIT DEQUANTIZER (BPDQp)

BPDQp generalizes BPDN by imposing an ℓp residual constraint tailored to quantization and generalized Gaussian noise. Its stability is established through RIPp,2 conditions for compressible signals and bounded ℓp noise.

  • Decoder definition: BPDQp is a class of convex decoders that generalizes the BPDN fidelity term.The decoder minimizes a sparse representation subject to a residual constraint measured in ℓp.
  • Decoder definition: For p ≥ 1, BPDQp assumes the measurement noise has bounded ℓp norm and constrains the reconstruction residual accordingly.The fidelity model is matched to generalized Gaussian noise with shape parameter p, including uniform noise as a relevant case.
  • Stability result: BPDQp achieves ℓ2−ℓ1 instance optimality for compressible signals with measurements corrupted by bounded ℓp noise.The result is a stability guarantee relating reconstruction quality to signal compressibility and measurement error.
  • Stability result: This stability result holds when the sensing matrix satisfies the extended RIPp,2 for 2 ≤ p < ∞.The theorem considers sparse orders including K, 2K, and 3K and bounded ℓp measurement noise.

IV. EXAMPLE OF RIPp,2 MATRICES

The section shows that standard Gaussian random matrices can satisfy RIPp,2 with high probability, but the measurement requirement grows with p and becomes especially costly at p = ∞.

  • Gaussian matrices: Standard Gaussian random matrices satisfy RIPp,2 with high probability for 2 ≤ p < ∞ under a p-dependent measurement condition.The construction uses iid N(0,1) entries and achieves the property with probability exceeding 1−η.
  • Gaussian matrices: For 2 ≤ p < ∞, the required number of measurements grows polynomially in K log(N/K), with order p/2.Thus increasing p strengthens the measurement requirement relative to the p = 2 setting.
  • Gaussian matrices: At p = ∞, the measurement requirement grows exponentially in K log(N/K), while the associated norm scaling is Θp(m) = log m.This marks a substantially different growth regime from finite p.
  • Geometric role of RIPp,2: The RIPp,2 property approximately preserves decorrelation among sparse vectors with disjoint supports when m is sufficiently large relative to sparsity.A supporting lemma bounds the interaction of measurements of disjoint-support sparse vectors using RIP constants.
  • Proof boundary: The proof relies on the 2-smooth geometry of ℓp for p ≥ 2, so the stated stability argument does not extend formally to p = ∞.The paper notes that p = ∞ requires different analytical tools because ℓ∞ is not 2-smooth.

V. BPDQp AND QUANTIZATION ERROR REDUCTION

BPDQ_p adapts the fidelity constraint to uniform quantization and yields a quantization-noise error reduction under oversampled sensing, subject to RIP conditions and finite feasible p.

  • BPDQ_p analyzes quantized measurements using an ℓ_p fidelity bound calibrated for uniformly distributed quantization distortion.The bound is estimated for uniform random vectors and makes the original signal feasible with a stated probability.
  • Theorem 2 bounds reconstruction error by a compressibility term plus a noise term proportional to ϵ/µ_p,2.This requires the sensing matrix to satisfy the extended RIP_p,2 condition.
  • Oversampling Principle: In oversampled SGR sensing, the quantization-noise term is divided by √(p+1) when the oversampling factor m/K exceeds a minimum value.The result concerns uniform quantization and the ℓ2−ℓ1 instance-optimality relation.
  • Oversampling Principle: Increasing m/K supports RIP_p,2 for higher p and decreases the RIP radius δ, while the BPDN improvement eventually saturates.For BPDQ_p, the reconstruction-error term continues to be divided by √(p+1).
  • The choice of p is constrained because RIP_p,2 holds only over a finite interval [2,p_max] for a fixed oversampling factor.The paper therefore expects an optimal maximum p for each reconstruction problem and evaluates this effect experimentally.
  • Increasing p mainly reduces the quantization-noise contribution; it does not significantly reduce compressibility error when measurements are plentiful.The ℓ_p norm appears only in the fidelity term, which becomes closer to the quantization-consistency constraint as p approaches p_max.

VI. NUMERICAL IMPLEMENTATION

BPDQ_p is convex for p≥1, although the paper generally uses p≥2, and its iterative solver converges to a global minimum.

  • BPDQ_p is convex for p≥1, while the numerical treatment generally uses p≥2.
  • The described efficient iterative procedure converges to the global minimum of BPDQ_p for all p≥1.

A. Proximal Optimization

The proximal-optimization formulation splits BPDQ_p into sparsity and fidelity components and solves it with Douglas–Rachford operator splitting.

  • BPDQ_p is formulated as the sum of the ℓ1 objective and the indicator of the convex fidelity tube T^p(ϵ).The tube contains signals whose measurement residual has ℓ_p norm at most ϵ.
  • The solution satisfies a resolvent fixed-point equation involving the subdifferential of the combined convex function.The resolvent is identified with the proximity operator.
  • Douglas–Rachford splitting evaluates the separate resolvents for sparsity and fidelity instead of the combined resolvent.For BPDQ_p, the sparsity resolvent is soft-thresholding and the fidelity resolvent is projection onto T^p(ϵ).
  • The iteration converges to a point whose projection onto T^p(ϵ) solves BPDQ_p.

B. Proximity operator of the ℓp fidelity constraint

The fidelity projection is computed directly for p=2 and p=∞, and iteratively for intermediate p using KKT equations and Newton updates.

  • The projection onto the ℓ_p fidelity tube is computed with an iterative method for 2≤p≤∞.
  • The general affine projection is obtained through an iterative proximity-operator method whose convergence is linear for a frame and O(1/t) for a merely bounded matrix.
  • For p=2 and p=∞, the unit-ball projection has an explicit form; intermediate p requires the iterative procedure.
  • For 2<p<∞, the projection is obtained by solving a constrained minimization problem on the unit ℓ_p ball.
  • The KKT conditions form m+1 equations in the projected vector and Lagrange multiplier, which are solved using Newton's method.The Jacobian has a block-invertible structure that enables efficient updates.
  • The Newton implementation typically reaches machine-precision-comparable error in fewer than 10 iterations.

VII. EXPERIMENTS

The experiments evaluate BPDQ_p on sparse one-dimensional signals and image reconstruction, showing that its benefits depend on oversampling and extend empirically to TV-regularized Fourier recovery.

  • Sparse signal experiments: At lower oversampling factors, increasing p beyond a certain point degrades reconstruction performance.The paper relates this behavior to possible failure of the sensing matrix to satisfy RIPp,2 when p is too large.
  • Quantization consistency: Increasing p increases the quantization-consistency fraction, and for m/K = 40 the p = 10 residual histogram is closer to uniform on [−1/2, 1/2] than p = 2.Quantization consistency is defined by remeasured coefficients satisfying |(Φx̂)i − yi| < α/2.
  • Image reconstruction: Across 50 randomized trials, Figure 3 reports average SNR and SNR improvement over BPDN as functions of p; Figure 4 visually compares BPDN with BPDQp for p = 10.The visual comparison uses 100 × 100 pixel reconstruction details, while error bars in the reconstruction simulations indicate one standard deviation.
  • Image reconstruction: Although the image experiment lies outside the theory’s stated guarantees, BPDQp shows improvements in SNR and visual quality over BPDN.The theory lacks a proof that FΩ satisfies RIPp,2 and was developed for ℓ1 synthesis regularization rather than TV analysis regularization.

VIII. CONCLUSION AND FURTHER WORK

The conclusion presents BPDQp as a decoder class designed for quantized compressed sensing and reports theoretical and experimental error reductions in oversampled settings. It also identifies open questions about choosing p, matrix constructions, and broader quantization models.

  • VIII. CONCLUSION AND FURTHER WORK: BPDQp decoders were introduced and shown theoretically and experimentally to substantially reduce reconstruction error in oversampled settings.The conclusion frames this reduction as the central outcome relative to commonly used BPDN.
  • VIII. CONCLUSION AND FURTHER WORK: The optimal moment p may depend on the oversampling ratio and the precise compressed-sensing coding and decoding scenario.Characterizing this dependence could guide selection of the best BPDQp decoder.
  • VIII. CONCLUSION AND FURTHER WORK: The paper proposes investigating other RIPp,2 random-matrix constructions, including the Random Fourier Ensemble.This is identified as a second direction for further theoretical study.
  • VIII. CONCLUSION AND FURTHER WORK: Future work includes setting α from the bit budget, sensing matrix, and signal-energy prior, while incorporating quantizer saturation.The authors also seek to extend quantization consistency and the optimization fidelity term to non-uniform scalar quantization.

APPENDIX A

Appendix A develops probabilistic tools for showing that Gaussian sensing matrices satisfy an extended RIP involving ℓp norms. The argument combines concentration, ε-net discretization, and support-wise union bounds, then gives scaling conditions for p.

  • Proof strategy: Concentration of Lipschitz functions controls the random process for a fixed unit vector, after which an ε-net and union bound extend the result over each sparse support.The ε-net size contributes a factor bounded by (1 + 2/ε)^K.
  • Gaussian matrix construction: The proof analyzes Gaussian sensing matrices with independent standard-normal entries and establishes bounds over sparse vectors.The matrix is represented through independent Gaussian columns and standard Gaussian probability densities.
  • Proof strategy: For F(·) = ∥·∥p, the concentration scale is μp,2 = E∥ξ∥p, with Lipschitz value λp = 1 for p ≥ 2.The resulting bound is extended from net points to all vectors on a fixed support and then to all K-sparse vectors.
  • RIPp,2 scaling: The authors note that the measurement requirements may be pessimistic, but Proposition 1 still proves Gaussian matrices satisfy RIPp,2 over a certain range of p.The p = 2 case recovers the classical result, while the exponent 2/p may be too small in the bound.
  • RIPp,2 scaling: For 2 ≤ p < ∞, the proposition gives RIPp,2 control when δ2K is at least on the order of m^-2/p, subject to the stated constants and probability bounds.For fixed K, N, and η, the argument also yields δ = O(m^-1/p√log m).

APPENDIX C

Appendix C derives moment and geometric bounds used in the decoder analysis, including estimates for Gaussian ℓp norms and a generalized polarization argument. These ingredients support the final reconstruction-error bound.

  • Gaussian moment bounds: For independent Gaussian coordinates, the appendix derives bounds on E∥ξ∥p and Var∥ξ∥p^p for finite p.The variance expression scales linearly with the measurement dimension m.
  • Geometric inequalities: For ℓp with p ≥ 2, the proof uses p-convexity and 2-smoothness together with a duality mapping J; for ℓ2, the relation reduces to the polarization identity.The mapping is specified coordinatewise through Jr(u).
  • Geometric inequalities: The generalized geometric argument bounds interactions between disjoint sparse components using the RIPp,2 assumptions and a quadratic minimization step.The construction introduces u and v with disjoint supports and optimizes over a scalar t.
  • Recovery bound: The resulting recovery analysis bounds the reconstruction error ∥h∥2 by a compressibility term and a quantization term proportional to ϵ/μp,2.The displayed bound also depends on Cp and δ2K through the stated rational factors.
  • Recovery bound: The final error inequality explicitly combines signal-tail error e0(K) with the fidelity tolerance term involving ϵ/μp,2.This is the appendix’s stated endpoint after applying RIPp,2 and the sparse decomposition.
  • Gaussian moment bounds: The appendix uses concentration inequalities for bounded independent variables to establish probabilistic control of normalized Gaussian ℓp norms.The derivation introduces bounded variables proportional to αp|ξi|p and applies an exponential tail bound.
Loading 0902.2367v4…