Abstract:
We study symmetric spiked matrix models with respect to a general class of noise
distributions. Given a rank-1 deformation of a random noise matrix, whose entries
are independently distributed with zero mean and unit variance, the goal is to
estimate the rank-1 part. For the case of Gaussian noise, the top eigenvector of
the given matrix is a widely-studied estimator known to achieve optimal statistical
guarantees, e.g., in the sense of the celebrated BBP phase transition. However, this
estimator can fail completely for heavy-tailed noise.
In this work, we exhibit an estimator that works for heavy-tailed noise up to the
BBP threshold that is optimal even for Gaussian noise. We give a non-asymptotic
analysis of our estimator which relies only on the variance of each entry remaining
constant as the size of the matrix grows: higher moments may grow arbitrarily fast
or even fail to exist. Previously, it was only known how to achieve these guarantees
if higher-order moments of the noises are bounded by a constant independent of
the size of the matrix.
Our estimator can be evaluated in polynomial time by counting self-avoiding walks
via a color coding technique. Moreover, we extend our estimator to spiked tensor
models and establish analogous results.
