On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank-One Perturbations of Gaussian Tensors
We consider the following detection problem: given a realization of a symmetric matrix 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 that there is a planted principal submatrix B of dimension L for which all upper triangular variables are i.i.d. Gaussians with mean 1 and variance 1, whereas all other upper triangular elements of X not in B are i.i.d. Gaussians variables with mean 0 and variance 1. We refer to this as the 'Gaussian hidden clique problem'. When L = (1 + ) √ n ( > 0), it is possible to solve this detection problem with probability 1 − o n (1) by computing the spectrum of X and considering the largest eigenvalue of X. We prove that when L < (1 − ) √ n no algorithm that examines only the eigenvalues of X can detect the existence of a hidden Gaussian clique, with error probability vanishing as n → ∞. The result above is an immediate consequence of a more general result on rank-one perturbations of k-dimensional Gaussian tensors. In this context we establish a lower bound on the critical signal-to-noise ratio below which a rank-one signal cannot be detected.
This paper is about hypothesis testing of Gaussian Hidden Clique problem. It shows that, for any \epsilon, the case where there exists a planted clique of size L = (1-\epsilon) \sqrt{n} cannot be distinguished against the case where there is no hidden clique, using spectral methods. This complements the positive result of [12], where it is possible to distinguish the two cases using a spectral method, when L > (1+\epsilon) \sqrt{n}. The main technical contribution is a general analysis based on rank-1 perturbation of order-k symmetric Gaussian tensors, which may be of independent interest.Quality: The result is technically sound as far as I have checked. Clarity: The paper is well-written overall; I am confused about Equation (24) -- why does it follow directly from Lemma 5?Originality: Although the proof technique based on Lemma 2 is quite interesting, to be honest, I am not able to evaluate the novelty since I am not familiar with the relevant literature of proving such lower bound.Significance: the paper establishes an interesting result, which nicely complements the previous positive result on spectral methods. But the downside is that this is only a lower bound for ``spectral methods", which makes the usage rather restrictive. It seems that extending this lower bound to any efficient detection algorithm is not easy, since the technique heavily relies on the fact that the eigenvalues are conjugation-invariant.