On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors

Andrea Montanari, Daniel Reichman, Ofer Zeitouni

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…