Random matrix eigenvalue approximation depends on polynomial degree threshold
Eigenvalue and Eigenvector Approximation for Random Matrices Using Low-Degree Polynomials
Data Structures and Algorithms
Summary
Finding the top eigenvalue and eigenvector of large random matrices is important but challenging. This paper shows that using polynomial functions of the matrix, with degree above a certain threshold, can accurately approximate these quantities. The threshold depends on the matrix type and size, and their findings improve on common assumptions about how many steps iterative methods need. They use advanced math tools to precisely describe when and how well these approximations work.
What this means in practice
- •For numerical linear algebra developers: Improve iterative eigenvector algorithms by selecting polynomial degrees based on matrix size and spike strength for faster convergence.
- •For statistical signal processors: Refine methods for detecting signals in noisy data using polynomial-based eigenvalue approximations tuned to noise and signal characteristics.
Tested on simulated data.
Authors
Yihan Zhang
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 = λvv^\top + X $, we identify $ d_\star = \frac{\log(n)}{2\log(λ)} $ 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 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.