Convergence rate of optimal quantization and application to the clustering performance of the empirical measure

MaRDI QIDQ4969145zbMATH OpenFDO

Authors Yating Liu, Gilles Pagès

Publication date 5 October 2020

Full work available at URL https://arxiv.org/abs/1811.08351, https://jmlr.csail.mit.edu/papers/v21/18-804.html

zbMATH Keywords

distortion functionoptimal quantizationempirical measureclustering performanceconvergence rate of optimal quantization

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Approximations to statistical distributions (nonasymptotic) (62E17)

Abstract: We study the convergence rate of the optimal quantization for a probability measure sequence $(m{u}_n{)}_{ninmathbb{N}^{\ast }}$ on $mathbb{R}^d$ converging in the Wasserstein distance in two aspects: the first one is the convergence rate of optimal quantizer $x^{(n)}in(mathbb{R}^d{)}^K$ of $m{u}_n$ at level $K$; the other one is the convergence rate of the distortion function valued at $x^{(n)}$, called the "performance" of $x^{(n)}$. Moreover, we also study the mean performance of the optimal quantization for the empirical measure of a distribution $mu$ with finite second moment but possibly unbounded support. As an application, we show that the mean performance for the empirical measure of the multidimensional normal distribution $mathcalN(m,Sigma)$ and of distributions with hyper-exponential tails behave like $mathcalO(fraclognsqrtn)$. This extends the results from [BDL08] obtained for compactly supported distribution. We also derive an upper bound which is sharper in the quantization level $K$ but suboptimal in $n$ by applying results in [FG15].

Recommendations

• On the mean speed of convergence of empirical and occupation measures in Wasserstein distance
• Individual Convergence Rates in Empirical Vector Quantizer Design
• Asymptotics of optimal quantizers for some scalar distributions
• Convergence of Vector Quantizers with Applications to Optimal Quantization
• Rates of convergence for the empirical quantization error

Cites work

• scientific article; zbMATH DE number 1166155 (Why is no real title available?)
• scientific article; zbMATH DE number 3803812 (Why is no real title available?)
• scientific article; zbMATH DE number 3244500 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• A central limit theorem for k-means clustering
• A note on a three-term recurrence for a tridiagonal matrix.
• A space quantization method for numerical integration
• Asymptotics of the maximal radius of an \(L^{r}\)-optimal sequence of quantizers
• Concentration inequalities. A nonasymptotic theory of independence
• Convergence of the one-dimensional Kohonen algorithm
• Exponential rate of convergence for Lloyd's method I
• Foundations of quantization for probability distributions
• Functional quantization rate and mean regularity of processes with an application to Lévy processes
• Introduction to vector quantization and its applications for numerics
• Least squares quantization in PCM
• Numerical probability. An introduction with applications to finance
• On the Performance of Clustering in Hilbert Spaces
• On the a.s. convergence of the Kohonen algorithm with a general neighborhood function
• On the rate of convergence in Wasserstein distance of the empirical measure
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• Pointwise convergence of the Lloyd I algorithm in higher dimension
• Quantization and the method of<tex>k</tex>-means
• Recursive computation of the invariant distribution of a diffusion
• Self-organization and a.s. convergence of the one-dimensional Kohonen algorithm with non-uniformly distributed stimuli
• Separability and completeness for the Wasserstein distance
• Strong consistency of k-means clustering
• Sufficient conditions for uniqueness of a locally optimal quantizer for a class of convex error weighting functions
• Uniqueness of locally optimal quantizer for log-concave density and convex error weighting function

Cited in

(3)

• Designing universal causal deep learning models: The geometric (Hyper)transformer
• Rates of convergence for the empirical quantization error
• Characterization of probability distribution convergence in Wasserstein distance by \(L^p\)-quantization error function

This page was built for publication: Convergence rate of optimal quantization and application to the clustering performance of the empirical measure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4969145)