Optimal random quantisers improve data compression for spherical data
Optimal random quantisers for spherically symmetric distributions
Machine Learning
Summary
This paper addresses how to best simplify complex, multi-dimensional data that looks the same in all directions, like points on a sphere. The authors show that picking random points evenly spread on a sphere can make these simplifications very effective, especially when you only have a moderate number of points to work with. They also provide a clear way to find the best size of this sphere to minimise errors and explain how the error behaves as you use more points. Their work supports better data compression methods for this kind of symmetrical data.
What this means in practice
- •For signal processing engineers: Design efficient data compression schemes for signals modeled by spherical distributions using optimally sized random quantisers.
- •For computer graphics developers: Use random quantisers on spheres to reduce the complexity of rendering or storing spherical data like lighting directions or 3D shape features.
Authors
Luc Pronzato, Anatoly Zhigljavsky
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$.