Convergence ponctuelle de l'algorithme de Lloyd en dimension supérieure.

Résumé Nous établissons la convergence ponctuelle de l'algorithme itératif de Lloyd, également connu sous le nom d'algorithme $k$-means, lorsque l'erreur de quantification quadratique de la grille de départ (de taille $N\ge 2$) est inférieure à l'erreur de quantification minimale par rapport à la distribution d'entrée est inférieure au niveau $N-1$. Un tel protocole est connu sous le nom de méthode de fractionnement et permet la convergence même lorsque la distribution d'entrée a un support non borné. Nous montrons également, sous une hypothèse très légère, que la grille limite résultante a toujours une taille complète de $N$. Ces résultats sont obtenus sans hypothèse de continuité sur la distribution d'entrée. Une variante de la procédure tirant avantage de l'asymptotique du rayon optimal du quantificateur est proposée, qui garantit toujours le caractère borné des grilles itérées.