Entrywise eigenvector analysis of random matrices with low expected rank (Q2196228)

This paper is a study on the analysis of eigenvector disturbance, which is a common problem in statistical machine learning. Many estimation problems in statistics involve low-rank matrix estimators that are NP-hard to calculate, and many of these estimators are solutions to nonconvex programs. The authors investigate entrywise behaviors of eigenvectors for a large class of random matrices whose expectations are low rank, which helps to settle a conjecture that the spectral algorithm achieves exact recovery in the stochastic block model without any trimming or cleaning steps. They investigate entry behaviors, self-spaces, for random matrices with low expected rank. The \( \ell_\infty \) distance between the eigenvectors of a random matrix and its expected counterparts may not be the correct to look at; input errors can be distributed asymmetrically. Let \(A\) be a random matrix, \(A^{\ast}=\mathbb{E}(A)\) and \(E = A - A^{\ast}\) be the ``error'' of \(A\), \(A\) symmetric, \(u_k\), respectively \(u_k^{\ast}\), be the eigenvector corresponding to the \(k\)-th largest eigenvalue of \(A\), respectively \(A^{\ast}\). If \(E\) is moderate, hence \(u_k=\displaystyle\frac{Au_k^{\ast}}{\lambda_k}\approx\displaystyle\frac{Au_k^{\ast}}{\lambda_k^{\ast}}=u_k^{\ast}+\frac{Eu_k^{\ast}}{\lambda_k^{\ast}}\). This perturbation analysis leads to new and sharp theoretical guarantees. To obtain such results, the authors characterize the concentration properties of \( A \) and structural assumptions in their expectation \( A^{\ast} \). For the exact recovery problem in the stochastic block model, the vanilla spectral algorithm reaches the theoretical limit of the information and coincides with the MLE estimator whenever it is successful. Therefore, MLE and SDP have no advantage over the spectral method in terms of exact recovery if the model is correct.