Optimal random quantisers for spherically symmetric distributions

Luc Pronzato; Anatoly Zhigljavsky

math.STOct 8, 2026

Optimal random quantisers for spherically symmetric distributions

Authors: Luc Pronzato, Anatoly Zhigljavsky

Organizations: Laboratoire I3S, CNRS-Université Côte d’Azur, Sophia Antipolis, France · School of Mathematics, Cardiff University, UK

Abstract

Zador's celebrated theorem is a cornerstone of optimal quantisation: it establishes both the weak limit of the empirical distribution of an optimal $n$ -point quantiser in $R^d$ and the decay rate of the associated $L_s$ -mean quantisation error. In large dimension, however, observing this asymptotic behaviour requires an astronomically large sample size. We prove that, for spherically symmetric target distributions, optimisation over all spherically symmetric distributions is a convex problem and derive an equivalence theorem that both characterises global optimality and yields a constructive algorithm. We show that, for moderate $n$ , random quantisers uniformly distributed on a sphere of suitably chosen radius $R$ perform exceptionally well and, over a broad range of values of $n$ , are numerically certified to be optimal among all random quantisers. Their expected distortion has an explicit integral representation that can be evaluated to arbitrary precision, and we prove concentration across random quantisers: the distortion variance tends to zero as $n\to\infty$ for fixed $d$ . For $s=2$ , both the optimal radius and the associated minimum expected distortion admit exact expressions. For general $s$ , the optimal radius can be determined efficiently, and extreme-value theory provides useful approximations when $n$ grows with $d$ . Depending on this growth rate, $R$ either converges to zero or approaches a positive limit that is independent of $s$ .

Figures & tables

Figure 1: Sphere. Smallest $n=n(d,s)$ such that $\mathbb{P}$ uniform on ${\mathcal{S}}_{d-1}(a^{*})$ is optimal, for $s=2$ ( $\blacklozenge$ ), $s=4$ ( $\bigstar$ ) and $s=10$ ( $\bullet$ ).

Panel of Figure 2 — Figure 2: Sphere. Value $a^{*}$ minimising $D_{\mu,s}(\mathbb{P}^{[n]}_{a})$ (left column) and ratio $D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a^{*}})/D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{1})$ (right column) as functions of $d$ for $s=2$ (top row) and $s=10$ (bottom row) and different values of $n$ : $n=10$ ( $\bullet$ ), $n=10^{2}$ ( $\blacklozenge$ ), $n=10^{3}$ ( $\blacktriangledown$ ), $n=10^{4}$ ( $\bigstar$ ), and $n=10^{5}$ ( $\blacksquare$ ). On the top-left panel, the dashed lines correspond to the extreme-value approximation ( 42 ) of Corollary 4.1 .

Panel of Figure 3 — Figure 3: Ball, $d=8$ . Sensitivity function $S_{\mu,2}(\rho;\Phi^{*},n)$ when $n=1\,000$ (left) and $n=100\,000$ (right).

Panel of Figure 4 — Figure 4: Ball, $s=2$ , $d=8$ . $\Phi^{*}$ ( — $\bullet$ ) and c.d.f. for $\mathbb{P}=\mu$ ( - - - $\blacklozenge$ ) when $n=1\,000$ (left) and $n=100\,000$ (right). The locations of the support points of $\Phi^{*}$ are indicated by $\bullet$ .

Panel of Figure 5 — Figure 5: $n_{1}(d,2)$ ( $\blacklozenge$ ), $n_{2}(d,2)$ ( $\bullet$ ) and $n_{3}(d,2)$ ( $\bigstar$ ) as functions of $d$ , for $\mu$ uniform on ${\mathscr{B}}_{d}(1)$ (left) and $\mu$ the normal distribution ${\mathcal{N}}(\mathbf{0}_{d},\mathbf{I}_{d}/d)$ (right).

Panel of Figure 6 — Figure 6: Normal distribution, $s=5$ , $d=10$ , $n=1\,000$ . Left: Sensitivity function $S_{\mu,5}(\rho;\Phi^{*},n)$ . Right: $\Phi^{*}$ ( — $\bullet$ ) and c.d.f. for $\mathbb{P}=\mu_{\sigma_{\infty}^{*}}$ ( - - - $\blacklozenge$ ); the locations of the support points of $\Phi^{*}$ are indicated by $\bullet$ .

Panel of Figure 7 — Figure 7: Optimal values $a^{*}(d,n,s)$ ( $\bullet$ ) and $\sigma^{*}(d,n,s)$ ( $\blacklozenge$ ) as functions of $s$ for $d=10$ and $n=1\,000$ (left panel, with $\sigma_{\infty}^{*}$ shown as a dashed line), and as functions of $d$ for $s=2$ and $n=10\,000$ (right panel).

Panel of Figure 8 — Figure 8: Values of $\kappa_{n,d}$ (left) and of $\widehat{a^{*}}(d,n,2)-a^{*}(d,n,2)$ (right) as functions of $d$ for different values of $n$ : $n=10^{2}$ ( $\blacklozenge$ ), $n=10^{3}$ ( $\blacktriangledown$ ), $n=10^{4}$ ( $\bigstar$ ) and $n=10^{5}$ ( $\blacksquare$ ).

Panel of Figure 9 — Figure 9: Relative error $1-\widehat{D}_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a})/D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a})$ of the approximation of $D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a})$ (left for $s=2$ and right for $s=4$ ) based on extreme-value theory, as a function of $d$ for different values of $n$ : $n=10^{2}$ ( $\blacklozenge$ ), $n=10^{3}$ ( $\blacktriangledown$ ), $n=10^{4}$ ( $\bigstar$ ) and $n=10^{5}$ ( $\blacksquare$ ); $a$ is the optimal value $a^{*}(d,n,s)$ .

Panel of Figure 10 — Figure 10: $n^{1/d}\,\widehat{D}_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a})$ ( $\blacklozenge$ ) and $n^{1/d}\,D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a})$ ( $\bullet$ ) as functions of $n$ for $s=4$ and $d=20$ . Left: $a=0.75$ for top curves and $a=a^{*}(d,n,s)$ for bottom curves. Right: $a=a^{*}(d,n,s)$ , the values of $n^{1/d}\,E_{\mu,s}(\mathbf{R}_{n})$ computed numerically for 100 random quantisers $\mathbf{R}_{n}\stackrel{{\scriptstyle d}}{{\sim}}\mathbb{P}^{[n]}_{a^{*}}$ are shown as magenta dots.

Panel of Figure 1 — Figure 1: Sphere. Value $a^{*}$ minimising $D_{\mu,s}(\mathbb{P}^{[n]}_{a})$ (left column), $D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a^{*}})$ (central column) and ratio $D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a^{*}})/D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{1})$ (right column) as functions of $d$ for $s=1$ (top row) and $s=10$ (bottom row) and different values of $n$ : $n=10$ ( $\bullet$ ), $n=10^{2}$ ( $\blacklozenge$ ), $n=10^{3}$ ( $\blacktriangledown$ ), $n=10^{4}$ ( $\bigstar$ ), and $n=10^{5}$ ( $\blacksquare$ ).

Explore similar work

Minimum Distortion Quantization with Specified Output Distribution
Jun 9, 2026Aolin XuRate-Distortion Theory Rate-Distortion Optimization
Provable Quantization with Randomized Hadamard Transform
May 13, 2026Ying Feng, Piotr Indyk, Michael Kapralov +2Vector Quantization Randomized Sketching
Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven
May 7, 2026Ran Ben-Basat, William Kuszmaul, Michael Mitzenmacher +2Rotation-Based Quantization Gradient Compression
UCL and Broadcom · Carnegie Mellon University · Harvard University +2

Jun 9, 2026, cs.ITJ/K move · Enter open · S save

Minimum Distortion Quantization with Specified Output Distribution

Aolin Xu

Rate-Distortion Theory Rate-Distortion Optimization

Open paper AskPDF arXiv

We derive the optimal quantizer of a real-valued random variable

W

with distribution

P_W

such that 1) the distribution of the quantization output

X

that can take

k

values follows any specified distribution

P_X

over

\{1,\ldots,k\}

, and 2) the minimum mean squared error (MMSE) of estimating

W

from

X

is minimized. It is shown that the optimal quantizer takes the form

X=σ\big(F_{σ^{-1}(X)}^{-1}(F_W(W))\big)

, where

σ

is the optimal permutation of

\{1,\ldots,k\}

among all permutations to minimize the MMSE, and

F

is the cumulative distribution function. When

P_W

is uniform over an interval or

P_X

is uniform over

\{1,\ldots,k\}

, the quantizer takes a simple form

X=F_{X}^{-1}(F_W(W))

. The concept of majorization plays a key role in the optimality proof. Specifying the output distribution is useful for designing quantizers with explicitly controlled output entropy, maximized mutual information between input and output, tailored output distribution to match channel input requirements for communication, and data anonymization.

Abstract

Explore similar work

Minimum Distortion Quantization with Specified Output Distribution

Provable Quantization with Randomized Hadamard Transform

Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven