= Solution
For a <symmetric matrix> $H$ with simple largest <eigenvalue> and <spectral gap> $\gamma$, the <Davis-Kahan curvature lemma> says $\frac\gamma2\|uu^\top-vv^\top\|_F^2\leq\operatorname{tr}(H(vv^\top-uu^\top))$, where $v$ is its leading unit <eigenvector>. Applying this to a leading <eigenvector> $\widehat v$ of $H+W$, the maximal <Rayleigh quotient> and duality of the <operator norm> and <trace norm> give $\|\widehat v\widehat v^\top-vv^\top\|_F\leq2\sqrt2\|W\|_{\mathrm{op}}/\gamma$; the projector difference has <matrix rank> at most two. This is a <rank-one eigenprojector perturbation bound>.
Here $W=M-M_0=A-A_0$ has independent centered bounded upper-triangular entries, apart from symmetry. The <spectral norm bound for a centered Bernoulli adjacency matrix> gives $\mathbb E\|W\|_{\mathrm{op}}\leq C_0\sqrt n$. Taking $H=M_0$ and $\gamma=t\sqrt n/2$ therefore gives, \b[for the largest-eigenvalue estimator],
$$
\boxed{\mathbb E\|\widehat v\widehat v^\top-vv^\top\|_F\leq\frac{4\sqrt2 C_0}{t}.}
$$
\b[The printed argmin selects the wrong end of the spectrum.] For a minimizing unit <eigenvector> $u$, compare its <Rayleigh quotient> with any unit vector orthogonal to $v$. This yields $\gamma|u^\top v|^2\leq2\|W\|_{\mathrm{op}}$, and hence $\mathbb E|u^\top v|^2\leq4C_0/t$. Its mean projector error is at least $\sqrt2(1-4C_0/t)$, using $\sqrt{1-x}\geq1-x$. Along $t=n^{1/4}$ with sufficiently large even $n$, the printed parameter restriction holds and this lower bound tends to $\sqrt2$, contradicting an error of order $1/t$. Replace argmin by argmax, or negate the entire matrix before minimizing.
Back to article page
