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.
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.
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
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 $\{...
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...
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...
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.