Pointwise convergence of the Lloyd I algorithm in higher dimension

DOI10.1137/151005622zbMATH Open1348.65037arXiv1401.0192OpenAlexW2266445751MaRDI QIDQ2820188FDOQ2820188

Authors: Gilles Pagès, Jun Yu 

Publication date: 14 September 2016

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

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.

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

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?

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)

Cites Work

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

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
• The resampling method via representative points
• Properties and generation of representative points of the exponential distribution
• 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)