Distributed noise-shaping quantization: I. Beta duals of finite frames and near-optimal quantization of random measurements

Research output: Contribution to journalArticlepeer-review


This paper introduces a new algorithm for the so-called "Analysis Problem" in quantization of finite frame representations which provides a near-optimal solution in the case of random measurements. The main contributions include the development of a general quantization framework called {\em distributed noise-shaping}, and in particular, {\em beta duals} of frames, as well as the performance analysis of beta duals in both deterministic and probabilistic settings. It is shown that for Gaussian random frames, using beta duals result in near-optimally accurate reconstructions with respect to both the frame redundancy and the number of levels that the frame coefficients are quantized at. More specifically, if $L$ quantization levels per measurement are used to encode the unit ball in $\mathbb{R}^k$ via a Gaussian frame of $m$ vectors, then with overwhelming probability the beta-dual reconstruction error is shown to be bounded by $\sqrt{k}L^{-(1-\eta)m/k}$ where $\eta$ is arbitrarily small for sufficiently large problems. Additional features of the proposed algorithm include low computational cost and parallel implementability.
Original languageUndefined
Article number1405.4628
StatePublished - May 19 2014


  • cs.IT
  • math.IT

Cite this