# Permutation recovery of spikes in noisy high-dimensional tensor estimation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 39 references that are in the map.
- First posted on arXiv 19 Dec 2024.

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

- [Prevalence of Neural Collapse during the terminal phase of deep learning training](https://mlsanity.com/paper/2008.08186/) (2020)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [High-dimensional limit theorems for SGD: Effective dynamics and critical scaling](https://mlsanity.com/paper/2206.04030/) (2022)
- [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)
- [Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval](https://mlsanity.com/paper/1910.12837/) (2019)
- [Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models](https://mlsanity.com/paper/1807.00891/) (2018)
- [Statistical limits of spiked tensor models](https://mlsanity.com/paper/1612.07728/) (2016)
- [Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitions](https://mlsanity.com/paper/1804.02686/) (2018)
- [Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares](https://mlsanity.com/paper/1705.02973/) (2017)
- [The Kikuchi Hierarchy and Tensor PCA](https://mlsanity.com/paper/1904.03858/) (2019)
- [Long Random Matrices and Tensor Unfolding](https://mlsanity.com/paper/2110.10210/) (2021)
- [Stochastic gradient descent in high dimensions for multi-spiked tensor PCA](https://mlsanity.com/paper/2410.18162/) (2024)
- [Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA](https://mlsanity.com/paper/2408.06401/) (2024)
- [Sharp Analysis of Power Iteration for Tensor PCA](https://mlsanity.com/paper/2401.01047/) (2024)

## Abstract (arXiv)

We study the dynamics of gradient flow in high dimensions for the multi-spiked tensor problem, where the goal is to estimate r unknown signal vectors (spikes) from noisy Gaussian tensor observations. Specifically, we analyze the maximum likelihood estimation procedure, which involves optimizing a highly nonconvex random function. We determine the sample complexity required for gradient flow to efficiently recover all spikes, without imposing any assumptions on the separation of the signal-to-noise ratios (SNRs). More precisely, our results provide the sample complexity required to guarantee recovery of the spikes up to a permutation. Our work builds on our companion paper [Ben Arous, Gerbelot, Piccolo 2024], which studies Langevin dynamics and determines the sample complexity and separation conditions for the SNRs necessary for ensuring exact recovery of the spikes (where the recovered permutation matches the identity). During the recovery process, the correlations between the estimators and the hidden vectors increase in a sequential manner. The order in which these correlations become significant depends on their initial values and the corresponding SNRs, which ultimately determines the permutation of the recovered spikes.