# On Estimating Rank-One Spiked Tensors in the Presence of Heavy Tailed Errors

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 48 references that are in the map.
- First posted on arXiv 20 Jul 2021.

## Builds on (most cited first, 12 of 12)

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015)
- [The landscape of the spiked tensor model](https://mlsanity.com/paper/1711.05424/) (2017)
- [Can parametric statistical methods be trusted for fMRI based group studies?](https://mlsanity.com/paper/1511.01863/) (2015)
- [Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries](https://mlsanity.com/paper/1605.07129/) (2016)
- [User-Friendly Covariance Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/1811.01520/) (2018)
- [Characterizing Spatiotemporal Transcriptome of Human Brain via Low Rank Tensor Decomposition](https://mlsanity.com/paper/1702.07449/) (2017)
- [Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks](https://mlsanity.com/paper/2008.13735/) (2020)
- [Perturbation Bounds for (Nearly) Orthogonally Decomposable Tensors](https://mlsanity.com/paper/2007.09024/) (2020)

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

- [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)
- [Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model](https://mlsanity.com/paper/2207.04600/) (2022)
- [Optimizing Orthogonalized Tensor Deflation via Random Tensor Theory](https://mlsanity.com/paper/2302.05798/) (2023)
- [On the Accuracy of Hotelling-Type Tensor Deflation: A Random Tensor Analysis](https://mlsanity.com/paper/2211.09004/) (2022)
- [A Nested Matrix-Tensor Model for Noisy Multi-view Clustering](https://mlsanity.com/paper/2305.19992/) (2023)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [On the Accuracy of Hotelling-Type Asymmetric Tensor Deflation: A Random Tensor Analysis](https://mlsanity.com/paper/2310.18717/) (2023)
- [On Spectral Learning for Odeco Tensors: Perturbation, Initialization, and Algorithms](https://mlsanity.com/paper/2509.25126/) (2025)
- [Heteroskedastic Canonical Polyadic Tensor Decomposition](https://mlsanity.com/paper/2610.00498/) (2026)

## Abstract (arXiv)

In this paper, we study the estimation of a rank-one spiked tensor in the presence of heavy tailed noise. Our results highlight some of the fundamental similarities and differences in the tradeoff between statistical and computational efficiencies under heavy tailed and Gaussian noise. In particular, we show that, for p th order tensors, the tradeoff manifests in an identical fashion as the Gaussian case when the noise has finite 4(p-1) th moment. The difference in signal strength requirements, with or without computational constraints, for us to estimate the singular vectors at the optimal rate, interestingly, narrows for noise with heavier tails and vanishes when the noise only has finite fourth moment. Moreover, if the noise has less than fourth moment, tensor SVD, perhaps the most natural approach, is suboptimal even though it is computationally intractable. Our analysis exploits a close connection between estimating the rank-one spikes and the spectral norm of a random tensor with iid entries. In particular, we show that the order of the spectral norm of a random tensor can be precisely characterized by the moment of its entries, generalizing classical results for random matrices. In addition to the theoretical guarantees, we propose estimation procedures for the heavy tailed regime, which are easy to implement and efficient to run. Numerical experiments are presented to demonstrate their practical merits.