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

clusteringdata miningconvergence\(k\)-means algorithmcentroidal Voronoi tessellationoptimal vector quantizationdata sciencesLloyd's I algorithmradius 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

• 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?)
• A QUANTIZATION TREE METHOD FOR PRICING AND HEDGING MULTIDIMENSIONAL AMERICAN OPTIONS
• A central limit theorem for k-means clustering
• A quantization algorithm for solving multidimensional discrete-time optimal stopping problems
• A truncated Newton-based multigrid algorithm for centroidal Voronoi diagram calculation
• AN OPTIMAL MARKOVIAN QUANTIZATION ALGORITHM FOR MULTI-DIMENSIONAL STOCHASTIC CONTROL PROBLEMS
• About the multidimensional competitive learning vector quantization algorithm with constant gain
• 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
• 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 Performance of Clustering in Hilbert Spaces
• On the a.s. convergence of the Kohonen algorithm with a general neighborhood function
• Optimal Quantization for Finance: From Random Vectors to Stochastic Processes
• Optimal quadratic quantization for numerics: the Gaussian case
• 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

(9)

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

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)