Recovering low-rank structures via eigenvector perturbation analysis is a
common problem in statistical machine learning, such as in factor analysis,
community detection, ranking, matrix completion, among others. While a large
variety of bounds are available for average errors between empirical and
population statistics of eigenvectors, few results are tight for entrywise
analyses, which are critical for a number of problems such as community
detection.
This paper investigates entrywise behaviors of eigenvectors for a large class
of random matrices whose expectations are low-rank, which helps settle the
conjecture in Abbe et al. (2014b) that the spectral algorithm achieves exact
recovery in the stochastic block model without any trimming or cleaning steps.
The key is a first-order approximation of eigenvectors under the $\ell_\infty$
norm: $$u_k \approx \frac{A u_k^*}{\lambda_k^*},$$ where $\{u_k\}$ and
$\{u_k^*\}$ are eigenvectors of a random matrix $A$ and its expectation
$\mathbb{E} A$, respectively. The fact that the approximation is both tight and
linear in $A$ facilitates sharp comparisons between $u_k$ and $u_k^*$. In
particular, it allows for comparing the signs of $u_k$ and $u_k^*$ even if $\|
u_k - u_k^*\|_{\infty}$ is large. The results are further extended to
perturbations of eigenspaces, yielding new $\ell_\infty$-type bounds for
synchronization ($\mathbb{Z}_2$-spiked Wigner model) and noisy matrix
completion.

本文通过证明一类随机矩阵的特征向量的近似线性关系，为完全恢复固定堆砌模型的谱算法提供了第一种严格无修剪方法。