Statistical limits of spiked tensor models
Amelia Perry111The first two authors contributed equally. Email: This work is supported in part by NSF CAREER Award CCF-1453261 and a grant from the MIT NEC Corporation. Department of Mathematics, Massachusetts Institute of Technology Alexander S. Wein Email: This research was conducted with Government support under and awarded by DoD, Air Force Office of Scientific Research, National Defense Science and Engineering Graduate (NDSEG) Fellowship, 32 CFR 168a. Department of Mathematics, Massachusetts Institute of Technology Afonso S. Bandeira Email: Department of Mathematics and Center for Data Science, Courant Institute of Mathematical Sciences, New York University
Abstract
We study the statistical limits of both detecting and estimating a rank-one deformation of a symmetric random Gaussian tensor. We establish upper and lower bounds on the critical signal-to-noise ratio, under a variety of priors for the planted vector: (i) a uniformly sampled unit vector, (ii) i.i.d. $\pm 1$ entries, and (iii) a sparse vector where a constant fraction $\rho$ of entries are i.i.d. $\pm 1$ and the rest are zero. For each of these cases, our upper and lower bounds match up to a $1+o(1)$ factor as the order $d$ of the tensor becomes large. For sparse signals (iii), our bounds are also asymptotically tight in the sparse limit $\rho\to 0$ for any fixed $d$ (including the $d=2$ case of sparse PCA). Our upper bounds for (i) demonstrate a phenomenon reminiscent of the work of Baik, Ben Arous and Péché: an ‘eigenvalue’ of a perturbed tensor emerges from the bulk at a strictly lower signal-to-noise ratio than when the perturbation itself exceeds the bulk; we quantify the size of this effect. We also provide some general results for larger classes of priors. In particular, the large $d$ asymptotics of the threshold location differs between problems with discrete priors versus c
中文速览
对称随机高阶张量（tensor）中隐藏着一个低秩"信号"时，要多强的信号才能被统计方法察觉或恢复出来——这就是张量PCA的核心难题。本文针对三类不同的信号先验分布（均匀单位向量、±1随机向量、稀疏±1向量），分别给出了信噪比临界值的上界和下界，并证明当张量阶数 d 趋于无穷时两侧界相差仅为 1+o(1) 倍，从而在渐近意义上精确确定了信息论门槛。技术上的核心突破是一种新的"噪声条件化"二阶矩方法：通过在计算中剔除信号与噪声联合作用下的罕见"坏事件"，成功消除了此前多项工作中普遍存在的 √2 倍松弛；作为副产品，研究还揭示了高阶张量中类似 Baik-Ben Arous-Péché 矩阵相变的"推出效应"，即注入信号的射影范数尚未超过噪声范数时，张量的本征值就已能从背景噪声中凸显出来。这些结果为张量PCA乃至稀疏PCA等高维统计推断问题提供了迄今最精确的信息论基准，也为理解统计可行性与计算可行性之间差距奠定了理论基础。
原文 arXiv:1612.07728;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1612.07728v2