高维张量PCA中，SGD可逐步恢复多个信号向量。
Stochastic gradient descent in high dimensions for multi-spiked tensor PCA
- 通过低维相关性系统分析，追踪估计值与信号的演化。
- 样本数达 $N^{p-2}$ 时可完全恢复所有信号，符合算法阈值。
- 信号按强度顺序被逐个识别，适合高维多峰张量分析场景。
我们研究了多尖峰张量模型下在线随机梯度下降（SGD）的高维动态行为。该多指标模型源于具有多个尖峰的张量主成分分析（PCA）问题，目标是从 $p$-阶张量的噪声观测中，通过最大似然估计在 $N$ 维单位球内恢复 $r$ 个未知信号向量。我们确定了实现有效恢复所需的样本数量及信噪比（SNR）条件。结果表明，当样本数达到 $N^{p-2}$ 量级时，可实现所有尖峰的完整恢复，与一阶情形下的算法阈值一致 [Ben Arous, Gheissari, Jagannath 2020, 2021]。分析基于一个描述估计值与尖峰间相关性演化的低维系统，并控制动态中的噪声。我们发现尖峰以‘顺序消除’方式被恢复：一旦某个相关性超过临界阈值，共享行或列索引的所有相关性会迅速减小，从而允许下一个相关性增长至宏观尺度。其恢复顺序取决于初始值和对应SNR，导致精确恢复或尖峰排列的恢复。在矩阵情形（$p=2$）中，若SNR足够分离，则实现尖峰的精确恢复；若相等，则仅恢复其张成子空间。
原文摘要 · Abstract (English)
We study the high-dimensional dynamics of online stochastic gradient descent (SGD) for the multi-spiked tensor model. This multi-index model arises from the tensor principal component analysis (PCA) problem with multiple spikes, where the goal is to estimate $r$ unknown signal vectors within the $N$-dimensional unit sphere through maximum likelihood estimation from noisy observations of a $p$-tensor. We determine the number of samples and the conditions on the signal-to-noise ratios (SNRs) required to efficiently recover the unknown spikes from natural random initializations. We show that full recovery of all spikes is possible provided a number of sample scaling as $N^{p-2}$, matching the algorithmic threshold identified in the rank-one case [Ben Arous, Gheissari, Jagannath 2020, 2021]. Our results are obtained through a detailed analysis of a low-dimensional system that describes the evolution of the correlations between the estimators and the spikes, while controlling the noise in the dynamics. We find that the spikes are recovered sequentially in a process we term "sequential elimination": once a correlation exceeds a critical threshold, all correlations sharing a row or column index become sufficiently small, allowing the next correlation to grow and become macroscopic. The order in which correlations become macroscopic depends on their initial values and the corresponding SNRs, leading to either exact recovery or recovery of a permutation of the spikes. In the matrix case, when $p=2$, if the SNRs are sufficiently separated, we achieve exact recovery of the spikes, whereas equal SNRs lead to recovery of the subspace spanned by them.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。