Non-asymptotic quantisation of spherically symmetric distributions

2026-05-14 · Source: stat.ML updates on arXiv.org · Field: Science & Research — Mathematics & Computational Sciences · Depth: Expert, extended

Summary

This paper addresses the challenge of optimal quantisation in high dimensions ($d$), where Zador's theorem requires an astronomically large sample size ($n$) for its asymptotic behavior to be observed. It demonstrates that for spherically symmetric distributions, random quantisers uniformly distributed on a sphere of a suitable radius $R$ achieve exceptional performance for moderate $n$. The expected distortion, expressed as a triple integral, can be computed with arbitrary precision, and the optimal radius $R$ is efficiently determined numerically. Leveraging extreme-value theory, the authors derive approximations for $R$, particularly when $n$ scales with $d$, showing that $R$ may converge to zero or approach a limiting value $R_{\infty}$ depending on $n$'s growth rate. This framework provides a compelling alternative for generating nearly optimal quantisers in large $n$ and $d$ situations, offering significant benefits over classical greedy-packing algorithms and naive quantisers.

Key takeaway

For high-dimensional spherically symmetric data where Zador's asymptotic quantisation is impractical, a novel non-asymptotic method using random quantisers on an optimized sphere significantly reduces distortion. Optimal performance is achieved by tuning the quantiser's spherical radius, which, depending on the sample size's growth relative to dimension, can converge to zero, a specific fraction (e.g., sqrt(3)/2 for n=2^d), or the distribution's concentration radius. This framework offers a practical, high-performance alternative for generating nearly optimal quantisers, crucial for efficient data representation and compression in high-dimensional machine learning and signal processing applications.

Topics

• Quantisation
• Spherically Symmetric Distributions
• Zador's Theorem
• Extreme-Value Theory
• Quantisation Error

Best for: AI Scientist, Research Scientist

Related on AIssential

• On Stability and Decomposition of Sample Quantiles under Heavy-Tailed Distributions — This paper addresses the instability of sample quantiles, particularly Value-at-Risk (VaR), when estimated parameters like projection direction and quantile threshold are derived from heavy-tailed financial returns.
• The most beautiful formula not enough people understand — High-dimensional geometry reveals counterintuitive properties, with n-dimensional sphere volumes peaking then becoming infinitesimal.
• $L^2$ over Wasserstein: Statistical Analysis for Optimal Transport — The $L^{2}$ over Wasserstein space unifies optimal transport under statistical uncertainty, extending its geometric and flow properties to random measures.
• Fundamental Limits of Membership Inference Attacks on Machine Learning Models — Overfitting in non-linear regression increases MIA success, while data discretization can enhance model security.
• Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven — Composing multiple randomized Hadamard transforms effectively approximates uniform random rotations for quantization.
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond — A new framework and algorithm significantly improve the efficient approximation of Shapley values and semi-values.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.