Entrywise eigenvector analysis of random matrices with low expected rank

DOI10.1214/19-AOS1854zbMath1450.62066arXiv1709.09565OpenAlexW3043617248MaRDI QIDQ2196228

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

zbMATH Keywords

matrix completionrandom matricessynchronizationspectral analysiscommunity detectioneigenvector perturbationlow-rank structures

Mathematics Subject Classification ID

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

Related Items

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

Uses Software

• Wirtinger Flow

Cites Work

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