Permutation Recovery of Spikes in Noisy High-Dimensional Tensor Estimation
摘要
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. We analyze the maximum likelihood estimator, which corresponds to optimizing a high-dimensional, nonconvex random objective. Our main results determine the sample complexity and runtime required for gradient flow to efficiently recover all spikes, up to a permutation. We show that, during recovery, correlations between the estimators and true spikes increase sequentially, in an order depending on their initial value and on the associated signal-to-noise ratios (SNRs). This ordering determines the permutation under which the spikes are recovered. This work builds on our companion paper [4], which analyzes Langevin dynamics and establishes the sample complexity and SNR conditions required for exact recovery, where the recovered permutation matches the identity.