Outliers in spectrum of sparse Wigner matrices

Konstantin Tikhomirov, Pierre Youssef

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we study the effect of sparsity on the appearance of outliers in the semi-circular law. Let (Formula presented.) be a sequence of random symmetric matrices such that each Wn is n × n with i.i.d. entries above and on the main diagonal equidistributed with the product (Formula presented.), where (Formula presented.) is a real centered uniformly bounded random variable of unit variance and bn is an independent Bernoulli random variable with a probability of success pn. Assuming that (Formula presented.), we show that for the random sequence (Formula presented.) given by (Formula presented.), the ratio (Formula presented.) converges to one in probability. A noncentered counterpart of the theorem allows to obtain asymptotic expressions for eigenvalues of the Erdős–Renyi graphs, which were unknown in the regime (Formula presented.). In particular, denoting by An the adjacency matrix of the Erdős–Renyi graph (Formula presented.) and by (Formula presented.) its kth largest (by the absolute value) eigenvalue, under the assumptions (Formula presented.) and (Formula presented.) we have (1) (No non-trivial outliers): if (Formula presented.) then for any fixed k ≥ 2, (Formula presented.) converges to 1 in probability; and (2) (Outliers): if (Formula presented.) then there is ε > 0 such that for any (Formula presented.), we have (Formula presented.). On a conceptual level, our result reveals similarities in appearance of outliers in spectrum of sparse matrices and the so-called BBP phase transition phenomenon in deformed Wigner matrices.

Original languageEnglish (US)
JournalRandom Structures and Algorithms
DOIs
StatePublished - 2020

Keywords

  • BBP phase transition
  • Erdos-Renyi graph
  • moment method
  • outliers
  • spectral gap

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Outliers in spectrum of sparse Wigner matrices'. Together they form a unique fingerprint.

Cite this