Universal entrywise eigenvector fluctuations in delocalized spiked matrix models and asymptotics of rounded spectral algorithms

Abstract

We consider the distribution of the top eigenvector $\hat{v}$ of a spiked matrix model of the form $H=\theta v{v}^{\ast }+W$, in the supercritical regime where $H$ has an outlier eigenvalue of comparable magnitude to $\Vert W\Vert$. We show that, if $v$ is sufficiently delocalized, then the distribution of the individual entries of the projector $\hat{v}{\hat{v}}^{\ast }$ (not, we emphasize, merely the inner product $|⟨\hat{v},v⟩{|}^2$) is universal over a large class of generalized Wigner matrices $W$ having independent entries, depending only on the first two moments of the distributions of the entries of $W$. This complements the observation of Capitaine and Donati-Martin (2021) that these distributions are not universal when $v$ is instead sufficiently localized. Further, for $W$ having entrywise variances close to constant and thus resembling a Wigner matrix, we show by comparing to $W$ drawn from the Gaussian orthogonal or unitary ensembles that averages of entrywise functions of $\hat{v}{\hat{v}}^{\ast }$ behave as they would if $\hat{v}$ had Gaussian fluctuations around a suitable multiple of $v$. We also establish such results for several possibly dependent spiked matrices, showing that, if such matrices are entrywise uncorrelated, then their leading eigenvectors behave as they would with independent Gaussian fluctuations. We apply these results to spectral algorithms with rounding procedures for synchronization problems over the cyclic and circle groups, obtaining the first precise asymptotic error rates for such algorithms. Using our analysis of multiple spiked matrices, we also show that multi-frequency spectral algorithms using estimates from several matrices often have asymptotic error rate superior to that of naive spectral algorithms using just one matrix.

64 pages, 7 figures. v2: Results expanded to include analysis of multi-spectral and multi-frequency algorithms, as well as other small corrections