Entrywise eigenvector analysis of random matrices with low expected rank

DOI10.1214/19-AOS1854zbMATH Open1450.62066arXiv1709.09565OpenAlexW3043617248MaRDI QIDQ2196228FDOQ2196228

Authors: Emmanuel Abbe, Kaizheng Wang, Yiqiao Zhong, Jianqing Fan 

Publication date: 28 August 2020

Published in: The Annals of Statistics (Search for Journal in Brave)

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 $el{l}_{i}nfty$ norm: ${\displaystyle }$u_k approx frac{A u_k^*}{lambda_k^*},${\displaystyle }$ where $u_k$ and $u_k^{*}$ are eigenvectors of a random matrix $A$ and its expectation $mathbbEA$, 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 $el{l}_{i}nfty$-type bounds for synchronization ($mathbb{Z}_2$-spiked Wigner model) and noisy matrix completion.

Full work available at URL: https://arxiv.org/abs/1709.09565

Recommendations

• An \(\ell_{\infty}\) eigenvector perturbation bound and its application
• Signal-plus-noise matrix models: eigenvector deviations and fluctuations
• Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
• Singular vectors under random perturbation
• Unperturbed: spectral analysis beyond Davis-Kahan

zbMATH Keywords

community detectionmatrix completionspectral analysisrandom matricessynchronizationeigenvector perturbationlow-rank structures

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Estimation in multivariate analysis (62H12) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Cites Work

• Matrix completion from noisy entries
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Spectral clustering and the high-dimensional stochastic blockmodel
• The Rotation of Eigenvectors by a Perturbation. III
• A proof of the block model threshold conjecture
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Matrix estimation by universal singular value thresholding
• Consistency of spectral clustering in stochastic block models
• Spectral redemption in clustering sparse networks
• Robust principal component analysis?
• Minimax rates of community detection in stochastic block models
• Title not available (Why is that?)
• Community Detection and Stochastic Block Models
• A Simple SVD Algorithm for Finding Hidden Partitions
• Community detection thresholds and the weak Ramanujan property
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Exact matrix completion via convex optimization
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• On semidefinite relaxations for the block model
• Exact Recovery in the Stochastic Block Model
• Perturbation bounds in connection with singular value decomposition
• Community detection in sparse networks via Grothendieck's inequality
• Consistency thresholds for the planted bisection model
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• Distributed 3-D Localization of Camera Sensor Networks From 2-D Image Measurements
• Matrix Completion From a Few Entries
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• One-Step Huber Estimates in the Linear Model
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Low-rank matrix completion using alternating minimization
• The largest eigenvalue of rank one deformation of large Wigner matrices
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• A spectral heuristic for bisecting random graphs
• Viewing direction estimation in cryo-EM using synchronization
• Angular synchronization by eigenvectors and semidefinite programming
• Guaranteed Matrix Completion via Non-Convex Factorization
• Asymptotics and concentration bounds for bilinear forms of spectral projectors of sample covariance
• Fundamental limits of symmetric low-rank matrix estimation
• Random Laplacian matrices and convex relaxations
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Phase transitions in semidefinite relaxations
• Proof of the Achievability Conjectures for the General Stochastic Block Model
• Semidefinite programs on sparse random graphs and their application to community detection
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• Asymptotic mutual information for the balanced binary stochastic block model
• Random perturbation of low rank matrices: improving classical bounds
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Perturbation of Linear Forms of Singular Vectors Under Gaussian Noise
• An $\ell_{\infty}$ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation
• Title not available (Why is that?)
• Near-Optimal Bounds for Phase Synchronization
• Spectral method and regularized MLE are both optimal for top-\(K\) ranking

Cited In (62)

• Statistical Significance of Clustering with Multidimensional Scaling
• Strong consistency guarantees for clustering high-dimensional bipartite graphs with the spectral method
• Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
• Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
• Rejoinder: “Co-citation and Co-authorship Networks of Statisticians”
• Clustering High-Dimensional Noisy Categorical Data
• Exact minimax optimality of spectral methods in phase synchronization and orthogonal group synchronization
• Leave-one-out singular subspace perturbation analysis for spectral clustering
• Special invited paper: the SCORE normalization, especially for heterogeneous network and text data
• Inference for heteroskedastic PCA with missing data
• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• Entrywise Estimation of Singular Vectors of Low-Rank Matrices With Heteroskedasticity and Dependence
• A Performance Guarantee for Spectral Clustering
• Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method
• Compressed spectral screening for large-scale differential correlation analysis with application in selecting glioblastoma gene modules
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• Normal approximation and confidence region of singular subspaces
• Non-convex exact community recovery in stochastic block model
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• On the smoothed analysis of the smallest singular value with discrete noise
• Uniform Bounds for Invariant Subspace Perturbations
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• Partial recovery for top-\(k\) ranking: optimality of MLE and suboptimality of the spectral method
• Robust high-dimensional factor models with applications to statistical machine learning
• A distributed community detection algorithm for large scale networks under stochastic block models
• Eigenvalues of the non-backtracking operator detached from the bulk
• Inference for low-rank models
• Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
• Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
• Title not available (Why is that?)
• Spectral method and regularized MLE are both optimal for top-\(K\) ranking
• Optimality of spectral clustering in the Gaussian mixture model
• Nonconvex Low-Rank Tensor Completion from Noisy Data
• Estimating Mixed Memberships With Sharp Eigenvector Deviations
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
• Eigen Selection in Spectral Clustering: A Theory-Guided Practice
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Model assisted variable clustering: minimax-optimal recovery and algorithms
• Rate optimal Chernoff bound and application to community detection in the stochastic block models
• The Interplay of Demographic Variables and Social Distancing Scores in Deep Prediction of U.S. COVID-19 Cases
• Singular vector distribution of sample covariance matrices
• Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
• Spectral clustering revisited: information hidden in the Fiedler vector
• Community detection on mixture multilayer networks via regularized tensor decomposition
• Hierarchical Community Detection by Recursive Partitioning
• Mixed Membership Estimation for Social Networks
• Using SVD for Topic Modeling
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
• An \({\ell_p}\) theory of PCA and spectral clustering
• Random graph asymptotics for treatment effect estimation under network interference
• Sharp optimal recovery in the two component Gaussian mixture model
• Iterative algorithm for discrete structure recovery

Uses Software

• Wirtinger Flow

This page was built for publication: Entrywise eigenvector analysis of random matrices with low expected rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196228)