Unified ${\ell }_{2\to \infty }$ Eigenspace Perturbation Theory for Symmetric Random Matrices

Abstract

Modern applications in statistics, computer science and network science have seen tremendous values of finer matrix spectral perturbation theory. In this paper, we derive a generic ${\ell }_{2\to \infty }$ eigenspace perturbation bound for symmetric random matrices, with independent or dependent entries and fairly flexible entry distributions. In particular, we apply our generic bound to binary random matrices with independent entries or with certain dependency structures, including the unnormalized Laplacian of inhomogenous random graphs and $m$-dependent matrices. Through a detailed comparison, we found that for binary random matrices with independent entries, our ${\ell }_{2\to \infty }$ bound is tighter than all existing bounds that we are aware of, while our condition is weaker than all but one of them in a less common regime. We apply our perturbation bounds in three problems and improve the state of the art: concentration of the spectral norm of sparse random graphs, exact recovery of communities in stochastic block models and partial consistency of divisive hierarchical clustering. Finally we discuss the extensions of our theory to random matrices with more complex dependency structures and non-binary entries, asymmetric rectangular matrices and induced perturbation theory in other metrics.

arXiv comment100 pages; typos corrected; Remark 2.3 added

References in corpus (13)

• Stochastic blockmodels with growing number of classes
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
• Near-optimal bounds for phase synchronization
• Guaranteed clustering and biclustering via semidefinite programming
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Finding Dense Clusters via "Low Rank + Sparse" Decomposition
• Estimating the number of communities in networks by spectral methods
• Unperturbed: spectral analysis beyond Davis-Kahan
• Estimating Mixed Memberships with Sharp Eigenvector Deviations
• Uniform bounds for invariant subspace perturbations
• Concentration Inequalities in Locally Dependent Spaces

Cited by in corpus (11)

• Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence
• Consistency of Spectral Clustering on Hierarchical Stochastic Block Models
• Optimal Spectral Recovery of a Planted Vector in a Subspace
• A useful criterion on studying consistent estimation in community detection
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models
• Linear regression and its inference on noisy network-linked data
• Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps
• Informative core identification in complex networks
• An ${\ell }_p$ theory of PCA and spectral clustering
• Directed degree corrected mixed membership model and estimating community memberships in directed networks