On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors
Andrea Montanari Department of Electrical Engineering and Department of Statistics, Stanford University. Partially supported by the NSF grant CCF-1319979 and the grants AFOSR/DARPA FA9550-12-1-0411 and FA9550-13-1-0036 Daniel Reichman Computer Science department, Cornell University, Ithaca, NY, 14853. Work done at the Weizmann Institute and supported in part by The Israel Science Foundation (grant No. 621/12) Ofer Zeitouni Faculty of Mathematics, Weizmann Institute, Rehovot 76100, Israel and Courant Institute, New York University. Partially supported by a grant from the Israel Science Foundation and the Herman P. Taubman chair of Mathematics at the Weizmann Institute.
Abstract
We consider the following detection problem: given a realization of a symmetric matrix $\mathbf{X}$ of dimension $n$ , distinguish between the hypothesis that all upper triangular variables are i.i.d. Gaussians variables with mean 0 and variance $1$ and the hypothesis where $\mathbf{X}$ is the sum of such matrix and an independent rank-one perturbation.
中文速览
在一个$n$维对称随机矩阵里藏着一个大小为$L$的"信号子矩阵"（高斯隐藏团问题），研究者想搞清楚：仅凭矩阵的特征值，到底能不能把"有信号"和"没信号"这两种情形可靠地区分开来？论文证明了一个精确的阈值：当$L \geq (1+\varepsilon)\sqrt{n}$时，盯着最大特征值就能检测出信号；而当$L < (1-\varepsilon)\sqrt{n}$时，任何只看特征值的检验方法都完全失效——其表现和随机猜测没有本质区别，这一结论通过建立似然比（likelihood ratio）的二阶矩有界性、并利用"竞争性"（contiguity）框架严格证明。更漂亮的是，作者把这一结果推广到了$k$阶高斯张量中秩一信号的检测问题，给出了信噪比的普适临界值，为机器学习中的张量分解任务提供了统计上的基本极限保障。
原文 arXiv:1411.6149;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1411.6149v1