Unified ℓ2→∞ Eigenspace Perturbation Theory for Symmetric Random Matrices

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 ℓ2→∞ 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 in homogenous random graphs and m-dependent matrices. Through a detailed comparison, we found that for binary random matrices with independent entries, our ℓ2→∞ 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.