Theorem 3 (Davis–Kahan, Yu–Wang–Samworth), p. 46, case s = 1 — ∃ orthogonal Ô, ‖U − ÛÔ‖_F ≤ 2^{3/2}‖Σ̂ − Σ‖_F / g

This is the Davis–Kahan $\sin\Theta$ theorem in the Frobenius-norm form of Yu, Wang and Samworth, for the leading eigenspace.

Let $\Sigma, \hat\Sigma \in \mathbb R^{n\times n}$ be symmetric. Let $U \in \mathbb R^{n \times r}$ have orthonormal columns that are eigenvectors of $\Sigma$, $\Sigma U = U\,\mathrm{Diag}(\lambda_1,\dots,\lambda_r)$, and suppose there is an eigengap $g > 0$ below them: for every $v$ orthogonal to the columns of $U$ and every $k$,

i.e. $\lambda_r(\Sigma) - \lambda_{r+1}(\Sigma) \ge g$ (in particular the $\lambda_k$ are the $r$ largest eigenvalues). Let $\hat U \in \mathbb R^{n\times r}$ consist of orthonormal top-$r$ eigenvectors of $\hat\Sigma$. Then there is an orthogonal matrix $\hat O \in \mathbb R^{r\times r}$ with

In the proof of Theorem 2 this bounds the distance between the top eigenvectors of the estimated clustering matrix $\hat X$ and those of the true clustering matrix $X^0$, step (i) of (G.6).

Formalization Note The paper states the theorem for eigenvectors $s, \dots, r$ with gap $\min(\lambda_{s-1}-\lambda_s, \lambda_r - \lambda_{r+1})$; this item is the case $s = 1$ (where $\lambda_0 = \infty$), the only case the paper uses. Any $g$ with $0 < g \le \lambda_r - \lambda_{r+1}$ is allowed; taking $g$ equal to the gap gives (G.5). When $r = n$ the complement is $\{0\}$ and the gap hypothesis is vacuous, as $\lambda_{n+1} = -\infty$ on the page.