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 ${\ell }_{\infty }$ norm: $$u_k\approx \frac{A{u}_k^{\ast }}{{\lambda }_k^{\ast }},$$ where $\{u_k\}$ and $\{u_k^{\ast }\}$ 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^{\ast }$. In particular, it allows for comparing the signs of $u_k$ and $u_k^{\ast }$ even if $\Vert u_k-u_k^{\ast }{\Vert }_{\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.

58 pages, 7 figures

References in corpus (7)

• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Near-optimal bounds for phase synchronization
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Distributed Estimation of Principal Eigenspaces
• The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
• Eigenvector Under Random Perturbation: A Nonasymptotic Rayleigh-Schrödinger Theory

Cited by in corpus (27)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Mixed Membership Estimation for Social Networks
• Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
• Principal component analysis for big data
• Unified ${\ell }_{2\to \infty }$ Eigenspace Perturbation Theory for Symmetric Random Matrices
• Estimating Mixed Memberships with Sharp Eigenvector Deviations
• Robust high dimensional factor models with applications to statistical machine learning
• Consistency of Spectral Clustering on Hierarchical Stochastic Block Models
• Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization
• Detecting Latent Communities in Network Formation Models
• Uniform bounds for invariant subspace perturbations
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Linear regression and its inference on noisy network-linked data
• On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models
• Learning Treatment Effects in Panels with General Intervention Patterns
• A Schatten-$q$ Low-rank Matrix Perturbation Analysis via Perturbation Projection Error Bound
• Incrementally Updated Spectral Embeddings
• Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
• Robust spectral compressive sensing via vanilla gradient descent
• Individual-centered partial information in social networks
• Theory of Spectral Method for Union of Subspaces-Based Random Geometry Graph
• Compressed spectral screening for large-scale differential correlation analysis with application in selecting Glioblastoma gene modules