Computer Science Theory Seminar
Aaron Potechin
University of Chicago
On the Spectrum of the Singular Values of Z-Shaped Graph Matrices
Abstract: Graph matrices are a type of matrix whose entries are functions of a random input such as a $G(n,1/2)$ graph. Thus, graph matrices have entries which are random but are generally not independent. Mathematically, little is known about graph matrices except for rough norm bounds. While these rough norm bounds are sufficient for many applications, we can hope to analyze graph matrices more precisely.
Wigner’s Semicircle Law is a classic result in random matrix theory which says that if $M$ is an $n \times n$ symmetric matrix with random entries drawn independently from a distribution with mean 0 and variance 1 (and bounded moments) then as $n \to \infty$, the spectrum of the eigenvalues of $\frac{M}{\sqrt{n}}$ approaches $\frac{\sqrt{4-x^2}}{2\pi}$.
In this talk, I will describe an analogue of Wigner’s Semicircle Law for Z-shaped graph matrices. I will begin by introducing graph matrices and why they are useful. I will then give a derivation of Wigner’s Semicircle Law and describe how the analysis can be generalized to find the spectrum of the singular values of Z-shaped graph matrices. Finally, I will discuss our upcoming follow-up work on this topic and some open problems.
Wednesday April 6, 2022 at 4:00 PM in 612 SEO