Entrywise eigenvector analysis of random matrices with low expected rank

DOI10.1214/19-AOS1854MaRDI QIDQ2196228zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1709.09565, https://projecteuclid.org/euclid.aos/1594972825

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)

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^{\ast }$ 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^{\ast }$. In particular, it allows for comparing the signs of $u_k$ and $u_k^{\ast }$ even if $|u_k-u_k^{\ast }{|}_{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.

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

Cites work

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

Cited in

(65)

• Rejoinder: “Co-citation and Co-authorship Networks of Statisticians”
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
• Statistical Significance of Clustering with Multidimensional Scaling
• 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
• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
• Strong consistency guarantees for clustering high-dimensional bipartite graphs with the spectral method
• Compressed spectral screening for large-scale differential correlation analysis with application in selecting glioblastoma gene modules
• Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
• scientific article; zbMATH DE number 7415122 (Why is no real title available?)
• Spectral alignment of correlated Gaussian matrices
• Non-convex exact community recovery in stochastic block model
• On the smoothed analysis of the smallest singular value with discrete noise
• Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
• Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
• scientific article; zbMATH DE number 7370530 (Why is no real title available?)
• Eigen Selection in Spectral Clustering: A Theory-Guided Practice
• Robust high-dimensional factor models with applications to statistical machine learning
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• Signal-plus-noise matrix models: eigenvector deviations and fluctuations
• scientific article; zbMATH DE number 7626708 (Why is no real title available?)
• Model assisted variable clustering: minimax-optimal recovery and algorithms
• Optimality of spectral clustering in the Gaussian mixture model
• Entrywise Estimation of Singular Vectors of Low-Rank Matrices With Heteroskedasticity and Dependence
• Iterative algorithm for discrete structure recovery
• Rate optimal Chernoff bound and application to community detection in the stochastic block models
• Mixed Membership Estimation for Social Networks
• Inference for low-rank models
• Using SVD for Topic Modeling
• A distributed community detection algorithm for large scale networks under stochastic block models
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
• Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
• scientific article; zbMATH DE number 7415089 (Why is no real title available?)
• Spectral method and regularized MLE are both optimal for top-\(K\) ranking
• scientific article; zbMATH DE number 7370563 (Why is no real title available?)
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• The interplay of demographic variables and social distancing scores in deep prediction of U.S. COVID-19 cases
• Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
• Normal approximation and confidence region of singular subspaces
• Spectral clustering revisited: information hidden in the Fiedler vector
• Community detection on mixture multilayer networks via regularized tensor decomposition
• A performance guarantee for spectral clustering
• Estimating Mixed Memberships With Sharp Eigenvector Deviations
• Improved performance guarantees for orthogonal group synchronization via generalized power method
• Uniform Bounds for Invariant Subspace Perturbations
• Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
• Nonconvex Low-Rank Tensor Completion from Noisy Data
• Partial recovery for top-\(k\) ranking: optimality of MLE and suboptimality of the spectral method
• Singular vector distribution of sample covariance matrices
• Eigenvalues of the non-backtracking operator detached from the bulk
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• Hierarchical Community Detection by Recursive Partitioning
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• Eigenvector phase retrieval: recovering eigenvectors from the absolute value of their entries
• Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
• 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

Describes a project that uses

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)