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 (61)

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 ⋮ Special invited paper: the SCORE normalization, especially for heterogeneous network and text data ⋮ Inference for heteroskedastic PCA with missing data ⋮ Statistical Significance of Clustering with Multidimensional Scaling ⋮ Robust high-dimensional factor models with applications to statistical machine learning ⋮ Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees ⋮ Strong consistency guarantees for clustering high-dimensional bipartite graphs with the spectral method ⋮ Mixed Membership Estimation for Social Networks ⋮ Using SVD for Topic Modeling ⋮ Rejoinder: “Co-citation and Co-authorship Networks of Statisticians” ⋮ Clustering High-Dimensional Noisy Categorical Data ⋮ Leave-one-out singular subspace perturbation analysis for spectral clustering ⋮ Exact minimax optimality of spectral methods in phase synchronization and orthogonal group synchronization ⋮ 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

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