Title: Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank,
Abstract: 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 results provide tight bounds on the average errors between empirical
and population statistics of eigenvectors, fewer results are tight for
entrywise analyses, which are critical for a number of problems such as
community detection and ranking.
This paper investigates the entrywise perturbation analysis for a large class
of random matrices whose expectations are low-rank, including community
detection, synchronization ($\mathbb{Z}_2$-spiked Wigner model) and matrix
completion models. Denoting by $\{u_k\}$, respectively $\{u_k^*\}$, the
eigenvectors of a random matrix $A$, respectively $\mathbb{E} A$, the paper
characterizes cases for which $$u_k \approx \frac{A u_k^*}{\lambda_k^*}$$
serves as a first-order approximation under the $\ell_\infty$ norm. The fact
that the approximation is both tight and linear in the random matrix $A$ allows
for sharp comparisons of $u_k$ and $u_k^*$. In particular, it allows to compare
the signs of $u_k$ and $u_k^*$ even when $\| u_k - u_k^*\|_{\infty}$ is large,
which in turn allows to settle the conjecture in Abbe et al. (2016) that the
spectral algorithm achieves exact recovery in the stochastic block model
without any trimming or cleaning steps. The results are further extended to the
perturbation of eigenspaces, providing new bounds for $\ell_\infty$-type errors
in noisy matrix completion.