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 = λ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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Probability

• arXiv preprint · 23 September 2026

  KATOsuper: Surrogate-accelerated neural topology optimization with sensitivity-consistent Fourier neural operators

  Shengyu Yan and Jasmin Jelovica
• arXiv preprint · 24 September 2026

  Elucidating the Conformal Structure of the Brinkman Penalisation Method for Geometry-Adapted, Structure-Preserving Operator Learning of Hamiltonian PDEs

  Teo Deveney, Baige Xu and Takaharu Yaguchi
• arXiv preprint · 23 September 2026

  Sparse-Observation Atmospheric Thermal Forecasting with Physics-Informed Neural Networks for Climate-Aware Digital Twins

  Tannaz Goodarzvand Chegini, Elyas Shivanian, Behzad Karimi and 1 other
• arXiv preprint · 24 September 2026

  Convergence guarantees for Muon: New parameter regimes and generalizations

  Arthur C. B. de Oliveira, Dhruv D. Jatkar, Guilherme S. Vicinansa and 1 other
• arXiv preprint · 23 September 2026

  A Hybrid Iterative Deep Ritz Method for Elliptic Interface Problems

  Tianhao Hu, Bangti Jin, Fengru Wang and 1 other

All new papers in Probability