Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks
This addresses a critical limitation in robust signal estimation for heavy-tailed noise, which is common in real-world data like finance or sensor networks, representing a significant advance over prior methods that required bounded higher moments.
The paper tackles the problem of estimating rank-one spikes from heavy-tailed noise in symmetric spiked matrix models, achieving optimal statistical guarantees up to the BBP threshold even when higher moments of the noise are unbounded, and extends the results to spiked tensor models.
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.