Yihan Zhang

Eigenvalue / eigenvector approximation using low-degree polynomials

For an $n\times n$ real symmetric random matrix $X$, we study how well the top eigenvalue and eigenvector of $X$ can be approximated using $q(X)b$ where $q$ is a low-degree polynomial and $b$ is an independent standard Gaussian vector. This is motivated by the fact that for some statistical estimation problems with random data, there is a gap between the regime in which the problem is solvable information-theoretically and the regime in which it is solvable computationally efficiently; in the latter regime, the best-known efficient algorithms often involve a spectral procedure.

When $X$ is a spiked GOE with signal-to-noise ratio $\lambda$, we show that the precise degree of $q$ to well approximate the top eigenvalue and the associated eigenvector is $0.5 \log(n) / \log(\lambda)$. For the pure noise model where $X$ is GOE, we show that eigenvector approximation is significantly harder than eigenvalue approximation. The precise degree for accurate eigenvector approximation is shown to be of order $n^{1/3}$ and a precise approximation guarantee at the critical degree is also provided. If time permits, connections to a broader notion of computational hardness and to optimization for spin glasses will be discussed.