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

arXiv: https://arxiv.org/abs/2008.13735 · HTML: https://mlsanity.com/paper/2008.13735/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Aug 2020.

## Built on by (most cited first, 5 of 5)

- [On Estimating Rank-One Spiked Tensors in the Presence of Heavy Tailed Errors](https://mlsanity.com/paper/2107.09660/) (2021)
- [Tensor cumulants for statistical inference on invariant distributions](https://mlsanity.com/paper/2404.18735/) (2024)
- [Higher degree sum-of-squares relaxations robust against oblivious outliers](https://mlsanity.com/paper/2211.07327/) (2022)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [Detection-Recovery Gap for Planted Dense Cycles](https://mlsanity.com/paper/2302.06737/) (2023)

## Abstract (arXiv)

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.