Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks

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.

arXiv comment38 pages

References in corpus (5)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Tensor principal component analysis via sum-of-squares proofs
• How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA
• Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere

Cited by in corpus (2)

• On convergence of the cavity and Bolthausen's TAP iterations to the local magnetization
• Hypothesis testing with low-degree polynomials in the Morris class of exponential families