= Sign rounding bound for a unit eigenvector
{title2=$\Delta(\widehat S,S)\leq n\|\widehat v\widehat v^\top-vv^\top\|_F^2$}
Suppose $v_i=\pm1/\sqrt n$ encodes the true partition and $\widehat v$ is a unit estimated <eigenvector>. Every coordinate of the wrong sign contributes at least $1/n$ to $\min_{\sigma=\pm1}\|\widehat v-\sigma v\|_2^2=2(1-|\widehat v^\top v|)$. Since this is at most $2(1-|\widehat v^\top v|^2)$, which is the squared Frobenius distance between the rank-one <orthogonal projection matrices>, the bound follows. Coordinates estimated as zero may be assigned consistently to either group.
Back to article page
