Entrywise eigenvector analysis of random matrices with low expected rank

Emmanuel Auguste Abbe, Jianqing Fan, Kaizheng Wang, Yiqiao Zhong

Research output: Contribution to journalArticle

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, Bandeira and Hall (2014) 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 ℓ norm: Auk ukλ∗k , where {uk} and {uk} are eigenvectors of a random matrix A and its expectation EA, respectively. The fact that the approximation is both tight and linear in A facilitates sharp comparisons between uk and uk. In particular, it allows for comparing the signs of uk and uk even if uk - uk∞ is large. The results are further extended to perturbations of eigenspaces, yielding new ℓ- type bounds for synchronization (Z2-spiked Wigner model) and noisy matrix completion.

Original languageEnglish (US)
Pages (from-to)1452-1474
Number of pages23
JournalAnnals of Statistics
Volume48
Issue number3
DOIs
StatePublished - Jun 2020

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Community detection
  • Eigenvector perturbation
  • Low-rank structures
  • Matrix completion
  • Random matrices
  • Spectral analysis
  • Synchronization

Fingerprint Dive into the research topics of 'Entrywise eigenvector analysis of random matrices with low expected rank'. Together they form a unique fingerprint.

  • Cite this