Skip to content
Preprint

Eigenvalue and Eigenvector Approximation for Random Matrices Using Low-Degree Polynomials

Sep 2026 · 0 citations
Mathematics Computer Science

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.

View source

Similar papers

Sep 2026

Matrix-Vector Complexity of Low-Rank Approximation

The proof extends adaptive Wishart deferred decisions to a rectangular factor with a $k$-dimensional nullspace while persistence of small compression eigenvalues controls growing $p$ and the spectral endpoint.

Hai-Han Zhang, Wen-Dao Wu, Chen-Heng Zhang et al. · 1 citation
Preprint Sep 2026

Tight bounds for positive discrepancy via eigenvalues

Given an $n\times n$ symmetric matrix $M$ with largest eigenvalue $\lambda_1\geq 0$, it is easy to show that the solution of the optimisation problem $\max_{v\in [-1,1]^n}v^TMv$ is at most $\lambda_1 n$. We prove the following converse: if every $n'\times n'$ principal submatrix of $M$ has maximal eigenvalue at least $...

Oliver Janzer, István Tomon, Fredy Yip · 1 citation
Preprint Nov 2026

Critical characteristic-polynomial chaos for complex iid matrices

We prove convergence to critical Gaussian multiplicative chaos for characteristic-polynomial measures of complex iid matrices. Let $A_N=N^{-1/2}(\xi_{ij})$, with a fixed law satisfying $\mathbb E\xi=\mathbb E\xi^2=0$, $\mathbb E|\xi|^2=1$, and finite moments of every order; no density is assumed. On each fixed disk $\{...

Yin-Qi Cai, Xiang Fang, Feng Guo · 0 citations
Preprint Sep 2026

Localization Lengths for Two-Dimensional Random Band Matrices: Stretched-Exponential Lower Bounds

We consider $N \times N$ random band matrices $H = (H_{xy})$ with centered complex Gaussian entries, indexed by points $x,y$ on the two-dimensional discrete torus $(\mathbb{Z} / \sqrt{N} \mathbb{Z})^2$. The matrix entries $H_{xy}$ vanish whenever the distance between $x$ and $y$ exceeds a constant multiple of the bandw...

Xu-Jie Lai, Fan Yang · 0 citations
Preprint Sep 2026

On $e$-doubly stochastic matrices over hyperbolic (polynomial) systems

In the setting of a hyperbolic (polynomial) system $(\mathcal{V}, p, e)$ of degree $n$, an $n$-tuple $\mathbf{A} = \big[ a_1, a_2, \dots, a_n \big]$ is said to be an $e$-doubly stochastic $\mathcal{V}$-matrix if each $a_i$ belongs to the hyperbolicity cone, has trace $1$, and $a_1 + a_2 + \dots + a_n = e$. In this arti...

Juyoung Jeong, M. Gowda, S. Shukla · 0 citations
Preprint Sep 2026

Moments of random multiplicative functions with polynomial coefficients

Let $f$ be a Steinhaus random multiplicative function and let $g$ be a polynomial of degree $d$. Write $S_N=N^{-1/2}\sum_{n\le N}f(n)\,e(g(n))$. We prove a quantitative dichotomy for the moments of $S_N$: for each integer $s\ge 2$, either $\mathbb{E}|S_N|^{2s}$ is close to the Gaussian moment $s!$, or the coefficients...

Xin-Yu Wang · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.