Lloyd's Algorithm and convergence conditions

704 Views Asked by At

I need help understanding the following theorem about Lloyd's algorithm (Du's Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations, Theorem 2.6). Lloyd's algorithm is used to compute Centroidal Voronoi Tessellations.

Theorem: If the iterations in the Lloyd algorithm stay in a compact set, where the Lloyd map $\mathbb{T}$ is continuous, then the algorithm is globally convergent to a critical point of $\mathbb{H}$.

Here, $\mathbb{T}$ maps a set of generator points in a convex subset of $\mathbb{S}\subset\mathbb{R}^n$ to a new set of centroids also in $\mathbb{S}$. The function $\mathbb{H}$ is an energy function and it means that it decreases (until it reaches some minimum) over iterations.

My problem is understanding the premise. What does it mean by "If the iterations in the Lloyd algorithm stay in a compact set"? The new centroid by definition will remain within the convex set $\mathbb{S}$ so the generators are always inside a compact set. Does it means that every new point (generator) belongs to the same Voronoi cell as the iteration before?

1

There are 1 best solutions below

2
On BEST ANSWER

For $n$ generators in $d$-dimensional space, the Lloyd map is a function ${\bf T}: X\rightarrow X$ where $X\subset {\mathbb R}^{nd}$. $X$ is strict subset of ${\mathbb R}^{nd}$ since two generators cannot coincide, i.e. $X = \left\{ \{{\bf Z_i}\}_{i=1}^n\,|\, {\bf Z}_j \neq {\bf Z}_k \,{\rm for\, any}\, j \neq k \right\}$. This set $X$ is not compact (in the normal sense in ${\mathbb R}^{nd}$) since points in $X$ can be arbitrarily close to points where generators do not coincide (which are not in $X$). The theorem is referring to a compact subset of this domain (of the Lloyd map) in ${\mathbb R}^{nd}$, not the underlying space of the generators ${\mathbb R}^{d}$.

The theorem is saying that if the Lloyd iteration can be restricted to a compact subset of $X$, then any limit points of the algorithm are well-defined centroidal Voronoi tessellations. But this is almost a tautology: phrased another way it says "if the iterations stay in a set that does not contain any degenerate accumulation points, then iteration cannot approach any degenerate points".

The theorem appears to say something stronger: if iteration stays in a compact set, then there is a single limit and that limit is a centroidal Voronoi tessellation. But that overstates the "global convergence theorem" which really says that any limit point of the iteration is a centroidal Voronoi tessellation without guaranteeing a single limit. For reference, there is a relatively concise explanation of the "Global Convergence Theorem" here with a clearer description of the conclusions that can be drawn.