On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors
Andrea Montanari Thanks: 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 Thanks: 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 Thanks: 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.
原文 arXiv:1411.6149;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1411.6149v1