{"id":"arxiv/2609.28781","url":"https://arxiv.org/abs/2609.28781","tags":["math.PR","cs.DS","math.NA","math.ST"],"score":0,"title":"Eigenvalue and Eigenvector Approximation for Random Matrices Using Low-Degree Polynomials","domain":"math.PR","source":"arxiv","authors":["Yihan Zhang"],"reviews":0,"subject":"math.PR","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-23","reactions":{}}