Lemma 5 (Lei–Rinaldo Lemma 5.3), pp. 45–46, (G.4) — Σ_k |S_k|δ²_k ≤ 4(4 + 2ε)‖V − V̂‖²_F

This is the approximate k-means bound of Lei and Rinaldo.

Let $\varphi : [n] \to [r]$ be a labelling with membership matrix $\Theta^* = \Theta(\varphi) \in \mathbb M_{n,r}$ and clusters $G_k = \{i : \varphi(i) = k\}$, let $B^* \in \mathbb R^{r\times r}$ with rows $b^*_1,\dots,b^*_r$, and put $V = \Theta^* B^*$. Let $\hat V \in \mathbb R^{n\times r}$ be arbitrary, $\epsilon > 0$, and let $(\hat\Theta, \hat B) = (\Theta(a), B)$ be a $(1+\epsilon)$-approximate solution of the k-means problem on the rows of $\hat V$:

Let $\bar V = \hat\Theta\hat B$ with rows $\bar v_i$, and let $\delta_1, \dots, \delta_r \ge 0$ satisfy $\delta_k \le \min_{l\ne k}\|b^*_l - b^*_k\|$. With $\mathcal S_k = \{i \in G_k : \|\bar v_i - v_i\| \ge \delta_k/2\}$,

The lemma converts a Frobenius-norm perturbation of a k-means-feasible embedding into a count of points whose estimated centre is far from their true centre; in Theorem 2 it is applied to $V = U^0 O$ and $\hat V = \hat U$.

Formalization Note The page's $\delta_k$ is implicitly a nonnegative scale; $\delta_k \ge 0$ is stated explicitly, since for a negative $\delta_k$ every point of $G_k$ would lie in $\mathcal S_k$ and the bound fails at $\hat V = V$. Membership matrices are encoded by assignments. The second part of the lemma (the permutation claim) is the separate item theorem_2_permutation.