Probability Seminar: Yihan Zhang
| Dates: | 28 October 2026 |
|---|
| Times: | 15:00 - 16:00 |
|---|
| What is it: | Seminar |
|---|
| Organiser: | Department of Mathematics |
|---|
| Who is it for: | University staff |
|---|
|
Yihan Zhang (University of Bristol) will speak at the Probability seminar.
Title: Eigenvalue and Eigenvector Approximation for Random Matrices Using Low-Degree Polynomials
Abstract: We initiate the study of approximating the top eigenvalue and eigenvector of a random symmetric matrix $ A \in \mathbb{R}^{n\times n} $ using $ q(A)b $ where $q$ is a degree-$d$ polynomial and $b$ is a standard Gaussian vector independent of $A$. For spiked GOE $ Y = \lambda vv^\top + X $, we identify $ d_\star = \frac{\log(n)}{2\log(\lambda)} $ to be the critical degree threshold above which accurate approximation of the top eigenvalue and eigenvector is possible. This sharpens the common belief that spectral methods can be implemented by $ O(\log(n)) $-step power iterations and offers a precise connection between spectral methods and low-degree polynomial algorithms, a popular proxy for all polynomial-time algorithms. For GOE $X$, we identify $ d_\star = n^{1/3+o(1)} $ to be the critical degree threshold for top eigenvector approximation, whereas constant degree suffices for top eigenvalue approximation. Moreover, in the limit where $ d/n^{1/3} $ converges to a positive finite constant, we compute the exact asymptotic eigenvector approximation accuracy in terms of the expected squared overlap. These results significantly improve upon predictions made in randomized numerical linear algebra for deterministic data matrices that the iteration count of power methods with random initialization is governed by the inverse spectral gap. Technically, our analyses leverage extremal properties of Chebyshev polynomials and draw upon the rich literature of random matrix theory. Based on https://arxiv.org/abs/2609.28781 arxiv.org .
Travel and Contact Information
Find event
Frank Adams 2
Alan Turing Building
Manchester
