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

zbMATH Open1502.62076arXiv1811.08351MaRDI QIDQ4969145FDOQ4969145

Authors: Yating Liu, Gilles Pagès 

Publication date: 5 October 2020

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].

Full work available at URL: https://arxiv.org/abs/1811.08351

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

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)

Cites Work

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

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)