Pointwise convergence of the Lloyd I algorithm in higher dimension

DOI10.1137/151005622MaRDI QIDQ2820188zbMATH OpenOpenAlexFDO

Authors Gilles Pagès, Jun Yu

Publication date 14 September 2016

Published in SIAM Journal on Control and Optimization (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-means algorithmcentroidal Voronoi tessellationclusteringconvergencedata miningdata sciencesLloyd's I algorithmoptimal vector quantizationradius of a quantizersplitting initialization methodstationary quantizers

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Abstract: We establish the pointwise convergence of the iterative Lloyd algorithm, also known as $k$-means algorithm, when the quadratic quantization error of the starting grid (with size $Nge2$) is lower than the minimal quantization error with respect to the input distribution is lower at level $N-1$. Such a protocol is known as the splitting method and allows for convergence even when the input distribution has an unbounded support. We also show under very light assumption that the resulting limiting grid still has full size $N$. These results are obtained without continuity assumption on the input distribution. A variant of the procedure taking advantage of the asymptotic of the optimal quantizer radius is proposed which always guarantees the boundedness of the iterated grids.

Recommendations

• Nondegeneracy and Weak Global Convergence of the Lloyd Algorithm in $\mathbb{R}^d$
• On convergence of Lloyd's method I
• Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations
• Quantization/clustering: when and why does k-means work?
• How fast is the \(k\)-means method?

Cites work

• A central limit theorem for k-means clustering
• A quantization algorithm for solving multidimensional discrete-time optimal stopping problems
• A QUANTIZATION TREE METHOD FOR PRICING AND HEDGING MULTIDIMENSIONAL AMERICAN OPTIONS
• A truncated Newton-based multigrid algorithm for centroidal Voronoi diagram calculation
• About the multidimensional competitive learning vector quantization algorithm with constant gain
• AN OPTIMAL MARKOVIAN QUANTIZATION ALGORITHM FOR MULTI-DIMENSIONAL STOCHASTIC CONTROL PROBLEMS
• Approximation by quantization of the filter process and applications to optimal stopping problems under partial observation
• Asymptotics of the maximal radius of an \(L^{r}\)-optimal sequence of quantizers
• Centroidal Voronoi Tessellations: Applications and Algorithms
• Convergence of distributed asynchronous learning vector quantization algorithms
• Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations
• Exponential rate of convergence for Lloyd's method I
• Foundations of quantization for probability distributions
• scientific article; zbMATH DE number 5010399 (Why is no real title available?)
• scientific article; zbMATH DE number 467196 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• Improved error bounds for quantization based numerical schemes for BSDE and nonlinear filtering
• Introduction to vector quantization and its applications for numerics
• Least squares quantization in PCM
• Limit Points of Sequences in Metric Spaces
• Nondegeneracy and Weak Global Convergence of the Lloyd Algorithm in $\mathbb{R}^d$
• Numerical Approximation by Quantization of Control Problems in Finance Under Partial Observations
• Numerical method for impulse control of piecewise deterministic Markov processes
• On convergence of Lloyd's method I
• On the a.s. convergence of the Kohonen algorithm with a general neighborhood function
• On the Performance of Clustering in Hilbert Spaces
• Optimal quadratic quantization for numerics: the Gaussian case
• Optimal Quantization for Finance: From Random Vectors to Stochastic Processes
• Optimal quantization methods for nonlinear filtering with discrete-time observations
• Optimal stopping for partially observed piecewise-deterministic Markov processes
• Quantization balls and asymptotics of quantization radii for probability distributions with radial exponential tails
• Review of Methods Inspired by Algebraic-Multigrid for Data and Image Analysis Applications
• The local quantization behavior of absolutely continuous probabilities
• The strong law of large numbers for k-means and best possible nets of Banach valued random variables

Cited in

(11)

• Convex order, quantization and monotone approximations of ARCH models
• Properties and generation of representative points of the exponential distribution
• Product Markovian quantization of a diffusion process with applications to finance
• Characterization of probability distribution convergence in Wasserstein distance by \(L^p\)-quantization error function
• On convergence of Lloyd's method I
• Convergence rate of optimal quantization and application to the clustering performance of the empirical measure
• Stationary Heston model: calibration and pricing of exotics using product recursive quantization
• Quantizing Rare Random Maps: Application to Flooding Visualization
• The resampling method via representative points
• Improved error bounds for quantization based numerical schemes for BSDE and nonlinear filtering
• Improved algorithm for the optimal quantization of single- and multivariate random functions

This page was built for publication: Pointwise convergence of the Lloyd I algorithm in higher dimension

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