  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 distributed
noise-shaping, and in particular, beta duals of frames, as well as the
performance analysis of beta duals in both deterministic and probabilistic
settings. It is shown that for random frames, using beta duals results 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, for any frame $E$ of $m$ vectors in $\mathbb{R}^k$
except possibly from a subset of Gaussian measure exponentially small in $m$
and for any number $L \geq 2$ of quantization levels per measurement to be used
to encode the unit ball in $\mathbb{R}^k$, there is an algorithmic quantization
scheme and a dual frame together which guarantee a reconstruction error of at
most $\sqrt{k}L^{-(1-\eta)m/k}$, where $\eta$ can be arbitrarily small for
sufficiently large problems. Additional features of the proposed algorithm
include low computational cost and parallel implementability.
