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 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 ℓ _∞ norm: $u_k\approx \frac{A{u}_k^{*}}{{\lambda }_k^{*}},$ where {u _k } and $\left\{u_k^{*}\right\}$ are eigenvectors of a random matrix A and its expectation $EA$ , 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 ${\Vert u_k-u_k^{*}\Vert }_{\infty }$ is large. The results are further extended to perturbations of eigenspaces, yielding new ℓ _∞-type bounds for synchronization ( ${\mathbb{Z}}_2$ -spiked Wigner model) and noisy matrix completion.

Keywords: 62H12; Primary 62H25; community detection; eigenvector perturbation; low-rank structures; matrix completion; random matrices; secondary 60B20; spectral analysis; synchronization.

Fig 1:

The second eigenvector and its first-order approximation in SBM. Left: The histogram of coordinates of $\sqrt{n}{u}_2$ computed from a single realization of adjacency matrix A, where n is 5000, a is 4.5 and b is 0.25. Exact recovery is expected as coordinates form two well-separated clusters. Right: boxplots showing three different distance/errors (up to sign) over 100 realizations: (i) $\sqrt{n}{\Vert u_2-u_2^{*}\Vert }_{\infty }$, (ii) $\sqrt{n}{\Vert A{u}_2^{*}/{\lambda }_2^{*}-u_2^{*}\Vert }_{\infty }$, (iii) $\sqrt{n}{\Vert u_2-A{u}_2^{*}/{\lambda }_2^{*}\Vert }_{\infty \cdot }A{u}_2^{*}/{\lambda }_2^{*}$ is a good approximation of u₂ under ℓ_∞ norm even though ${\Vert u_2-u_2^{*}\Vert }_{\infty }$ may be large.

Fig 2:

Typical choices of φ for Gaussian noise and Bernoulli noise.

Fig 3:

Error decay in power iterations. The larger and smaller squares represent ℓ_∞ balls centered at $\overline{u}$, with radii ${\Vert u^0-\overline{u}\Vert }_{\infty }$ and ${\Vert u^1-\overline{u}\Vert }_{\infty }$, respectively.

Fig 4:

Eigen-gap Δ*

Fig 5:

Phase transition of ${\mathbb{Z}}_2$-synchronization: the x-axis is the dimension n, and the y-axis is σ. Lighter pixels refer to higher proportions of runs that $\widehat{x}$ recovers x. The red curve shows the theoretical boundary $\sigma =\sqrt{\frac{n}{2\log n}}$.

Fig 6:

Vanilla spectral method for SBM. Left: phase transition of exact recovery. The x-axis is b, the y-axis is a, and lighter pixels represent higher chances of success. Two red curves $\sqrt{a}-\sqrt{b}=\pm \sqrt{2}$ represent theoretical boundaries for phase transtion, matched by numerical results. Right: mean misclassification rates on the logarithmic scale with b = 2. The x-axis is a, varying from 2 to 8, and the y-axis is $\log \mathbb{E}r(\widehat{z},z)/\log n$. No marker: theoretical curve; circles: n = 5000; crosses: n = 500; squares: n = 100.

Fig 7:

R_mat and R_vec in matrix completion from noisy entries. The x-axis is n, varying from 500 to 5000 by 500, and the y-axis is the ratio. Crosses and circles stand for R_mat and R_vec, respectively.