Linear stability analysis of the Lloyd algorithm on a circle
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911726701641728 |
|---|---|
| author | Saha, Silpi Jha, Sangita Roychowdhury, Mrinal Kanti |
| author_facet | Saha, Silpi Jha, Sangita Roychowdhury, Mrinal Kanti |
| contents | Lloyd algorithm is the standard iterative method for computing quantizers and codebooks in source coding and vector quantization. In this article, we study the dynamical and stability properties of the Lloyd map on the unit circle $\mathbb S^1$ using von Mises distributions. We construct the Lloyd iteration as a discrete dynamical system on the configuration space of ordered point sets modulo rotational symmetry. Also, we study the rotational equivarience of the Lloyd map. Further, we derive an explicit representation of the Jacobian matrix and prove that it possesses a circulant structure for the equally spaced configuration. Also, we study the bifurcation characteristics based on Lloyd map analysis. In the end, we provide the numerical algorithms for stability diagrams, Lyapunov spectrum estimation, and residue analysis, purely for empirical visualization. Our results provide a dynamical systems framework for Lloyd quantization on $\mathbb S^1$ for studying stability properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_29451 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Linear stability analysis of the Lloyd algorithm on a circle Saha, Silpi Jha, Sangita Roychowdhury, Mrinal Kanti Dynamical Systems Optimization and Control Lloyd algorithm is the standard iterative method for computing quantizers and codebooks in source coding and vector quantization. In this article, we study the dynamical and stability properties of the Lloyd map on the unit circle $\mathbb S^1$ using von Mises distributions. We construct the Lloyd iteration as a discrete dynamical system on the configuration space of ordered point sets modulo rotational symmetry. Also, we study the rotational equivarience of the Lloyd map. Further, we derive an explicit representation of the Jacobian matrix and prove that it possesses a circulant structure for the equally spaced configuration. Also, we study the bifurcation characteristics based on Lloyd map analysis. In the end, we provide the numerical algorithms for stability diagrams, Lyapunov spectrum estimation, and residue analysis, purely for empirical visualization. Our results provide a dynamical systems framework for Lloyd quantization on $\mathbb S^1$ for studying stability properties. |
| title | Linear stability analysis of the Lloyd algorithm on a circle |
| topic | Dynamical Systems Optimization and Control |
| url | https://arxiv.org/abs/2605.29451 |