Sum-of-Squares Lower Bounds for Sparse PCA

Introduction

We start with a general discussion of the tension between sample size and computational efficiency in statistical and learning problems. We then describe the concrete model and problem at hand: Sum-of-Squares algorithms and the Sparse-PCA problem. All are broad topics studied from different viewpoints, and the given references provide more information.

Modern machine learning and statistical inference problems are often high dimensional, and it is highly desirable to solve them using far less samples than the ambient dimension. Luckily, we often know, or assume, some underlying structure of the objects sought, which allows such savings in principle. Typical such assumption is that the number of real degrees of freedom is far smaller than the dimension; examples include sparsity constraints for vectors, and low rank for matrices and tensors. The main difficulty that occurs in nearly all these problems is that while information theoretically the sought answer is present (with high probability) in a small number of samples, actually computing (or even approximating) it from these many samples is a computationally hard problem. It is often expressed as a non-convex optimization program which is NP-hard in the worst case, and seemingly hard even on random instances.

Given this state of affairs, relaxed formulations of such non-convex programs were proposed, which can be solved efficiently, but sometimes to achieve accurate results seem to require far more samples than existential bounds provide. This phenomenon has been coined the “statistical versus computational trade-off” by Chandrasekaran and Jordan [CJ13], who motivate and formalize one framework to study it in which efficient algorithms come from the Sum-of-Squares family of convex relaxations (which we shall presently discuss). They further give a detailed study of this trade-off for the basic de-noising problem [Joh02, Don95, DJ98] in various settings (some exhibiting the trade-off and others that do not). This trade-off was observed in other practical machine learning problems, in particular for the Sparse PCA problem that will be our focus, by Berthet and Rigollet [BR13a].

As it turns out, the study of the same phenomenon was proposed even earlier in computational complexity, primarily from theoretical motivations. Decatur, Goldreich and Ron [DGR97] initiate the study of “computational sample complexity” to study statistical versus computation trade-offs in sample-size. In their framework efficient algorithms are arbitrary polynomial time ones, not restricted to any particular structure like convex relaxations. They point out for example that in the distribution-free PAC-learning framework of Vapnik-Chervonenkis and Valiant, there is often no such trade-off. The reason is that the number of samples is essentially determined (up to logarithmic factors, which we will mostly ignore here) by the VC-dimension of the given concept class learned, and moreover, an “Occam algorithm” (computing any consistent hypothesis) suffices for classification from these many samples. So, in the many cases where efficiently finding a hypothesis consistent with the data is possible, enough samples to learn are enough to do so efficiently! This paper also provide examples where this is not the case in PAC learning, and then turns to an extensive study of possible trade-offs for learning various concept classes under the uniform distribution. This direction was further developed by Servedio [Ser00].

The fast growth of Big Data research, the variety of problems successfully attacked by various heuristics and the attempts to find efficient algorithms with provable guarantees is a growing area of interaction between statisticians and machine learning researchers on the one hand, and optimization and computer scientists on the other. The trade-offs between sample size and computational complexity, which seems to be present for many such problems, reflects a curious “conflict” between these fields, as in the first more data is good news, as it allows more accurate inference and prediction, whereas in the second it is bad news, as a larger input size is a source of increased complexity and inefficiency. More importantly, understanding this phenomenon can serve as a guide to the design of better algorithms from both a statistical and computational viewpoints, especially for problems in which data acquisition itself is costly, and not just computation. A basic question is thus for which problems is such trade-off inherent, and to establish the limits of what is achievable by efficient methods.

Establishing a trade-off has two parts. One has to prove an existential, information theoretic upper bound on the number of samples needed when efficiency is not an issue, and then prove a computational lower bound on the number of samples for the class of efficient algorithms at hand. Needless to say, it is desirable that the lower bounds hold for as wide a class of algorithms as possible, and that it will match the best known upper bound achieved by algorithms from this class. The most general one, the computational complexity framework of [DGR97, Ser00] allows all polynomial-time algorithms. Here one cannot hope for unconditional lower bounds, and so existing lower bounds rely on computational assumptions, e.g.”cryptographic assumptions”, e.g. that factoring integers has no polynomial time algorithm, or other average case assumptions. For example, hardness of refuting random 3CNF was used for establishing the sample-computational tradeoff for learning halfspaces [DLS13], and hardness of finding planted clique in random graphs was used for tradeoff in sparse PCA [BR13a, GMZ14]. On the other hand, in frameworks such as [CJ13], where the class of efficient algorithms is more restricted (e.g. a family of convex relaxations), one can hope to prove unconditional lower bounds, which are called “integrality gaps” in the optimization and algorithms literature. Our main result is of this nature, adding to the small number of such lower bounds for machine learning problems.

We now turn to describe and motivate SoS convex relaxations algorithms, and then the Sparse PCA problem.

2 Sum-of-Squares convex relaxations

Sum-of-Squares algorithms (sometimes called the Lasserre hierarchy) encompasses perhaps the strongest known algorithmic technique for a diverse set of optimization problems. It is a family of convex relaxations introduced independently around the year 2000 by Lasserre [Las01], Parillo [Par00], and in the (equivalent) context of proof systems by Grigoriev [Gri01b]. These papers followed better and better understanding in real algebraic geometry [Art27, Kri64, Ste74, Sho87, Sch91, Put93, Nes00]of David Hilbert’s famous 17th problem on certifying the non-negativity of a polynomial by writing it as a sum of squares (which explains the name of this method). We only briefly describe this important class of algorithms; far more can be found in the book [Las15] and the excellent extensive survey [Lau09].

The SoS method provides a principled way of adding constraints to a linear or convex program in a way that obtains tighter and tighter convex sets containing all solutions of the original problem. This family of algorithms is parametrized by their degree $d$ (sometimes called the number of rounds); as $d$ gets larger, the approximation becomes better, but the running time becomes slower, specifically $n^{O(d)}$. Thus in practice one hopes that small degree (ideally constant) would provide sufficiently good approximation, so that the algorithm would run in polynomial time. This method extends the standard semi-definite relaxation (SDP, sometimes called spectral), that is captured already by degree-2 SoS algorithms. Moreover, it is more powerful than two earlier families of relaxations: the Sherali-Adams [SA90] and Lovász-Scrijver [LS91] hierarchies.

The introduction of these algorithms has made a huge splash in the optimization community, and numerous applications of it to problems in diverse fields were found that greatly improve solution quality and time performance over all past methods. For large classes of problems they are considered the strongest algorithmic technique known. Relevant to us is the very recent growing set of applications of constant-degree SoS algorithms to machine learning problems, such as [BKS15, BKS14, BM15]. The survey [BS14] contains some of these exciting developments. Section 2.3 contains some self-contained material about the general framework SoS algorithms as well.

Given their power, it was natural to consider proving lower bounds on what SoS algorithms can do. There has been an impressive progress on SoS degree lower bounds (via beautiful techniques) for a variety of combinatorial optimization problems [Gri01a, Gri01b, Sch08, MPW15]. However, for machine learning problems relatively few such lower bounds (above SDP level) are known [BM15, WGL15] and follow via reductions to the above bounds. So it is interesting to enrich the set of techniques for proving such limits on the power of SoS for ML. The lower bound we prove indeed seem to follow a different route than previous such proofs.

3 Sparse PCA

Sparse principal component analysis, the version of the classical PCA problem which assumes that the direction of variance of the data has a sparse structure, is by now a central problem of high-diminsional statistical analysis. In this paper we focus on the single-spiked covariance model introduced by Johnstone [Joh01]. One observes $n$ samples from $p$-dimensional Gaussian distribution with covariance

where (the planted vector) $v$ is assumed to be a unit-norm sparse vector with at most $k$ non-zero entries, and $\lambda>0$ represents the strength of the signal. The task is to find (or estimate) the sparse vector $v$. More general versions of the problem allow several sparse directions/components and general covariance matrix [Ma13, VL13]. Sparse PCA and its variants have a wide variety of applications ranging from signal processing to biology: see, e.g., [ABN+99, JL09, Che11, JOB10].

The hardness of Sparse PCA, at least in the worst case, can be seen through its connection to the (NP-hard) Clique problem in graphs. Note that if $\Sigma$ is a $\{0,1\}$ adjacency matrix of a graph (with 1’s on the diagonal), then it has a $k$-sparse eigenvector $v$ with eigenvalue $k$ if and only if the graph has a $k$-clique. This connection between these two problems is actually deeper, and will appear again below, for our real, average case version above.

From a theoretical point of view, Sparse PCA is one of the simplest examples where we observe a gap between the number of samples needed information theoretically and the number of samples needed for a polynomial time estimator: It has been well understood [VL12, PJ12, BR13b] that information theoretically, given $n=O(k\log p)$ samplesWe treat $\lambda$ as a constant so that we omit the dependence on it for simplicity throughout the introduction section, one can estimate $v$ up to constant error (in euclidean norm), using a non-convex (therefore not polynomial time) optimization algorithm. On the other hand, all the existing provable polynomial time algorithms [JL09, AW09, VL13, DM14], which use either diagonal thresholding (for the single spiked model) or semidefinite programming (for general covariance), first introduced for this problem in [dGJL07], need at least quadratically many samples to solve the problem, namely $n=O(k^{2})$. Moreover, Krauthgamer, Nadler and Vilenchik [KNV15] and Berthet and Rigollet [BR13b] have shown that for semi-definite programs (SDP) this bound is tight. Specifically, the natural SDP cannot even solve the detection problem: to distinguish the data in equation 1.1 above from the null hypothesis in which no sparse vector is planted, namely the $n$ samples are drawn from the Gaussian distribution with covariance matrix $I$.

Recall that the natural SDP for this problem (and many others) is just the first level of the SoS hierarchy, namely degree-2. Given the importance of the Sparse PCA, it is an intriguing question whether one can solve it efficiently with far fewer samples by allowing degree-$d$ SoS algorithms with larger $d$. A very interesting conditional negative answer was suggested by Berthet and Rigollet [BR13b]. They gave an efficient reduction from Planted CliqueAn average case version of the Clique problem in which the input is a random graph in which a much larger than expected clique is planted. problem to Sparse PCA, which shows in particular that degree-$d$ SoS algorithms for Sparse PCA will imply similar ones for Planted Clique. Gao, Ma and Zhou [GMZ14] strengthen the result by establishing the hardness of the Gaussian single-spiked covariance model, which is an interesting subsetNote that lower bounds for special cases are stronger than those for general cases of models considered by [BR13a]. These are useful as nontrivial constant-degree SoS lower bounds for Planted Clique were recently proved by [MPW15, DM15] (see there for the precise description, history and motivation for Planted Clique). As [BR13b, GMZ14] argue, strong yet believed bounds, if true, would imply that the quadratic gap is tight for any constant $d$. Before the submission of this paper, the known lower bounds above for planted clique were not strong enough yet to yield any lower bound for Sparse PCA beyond the minimax sample complexity. We also note that the recent progress [RS15, HKP15] that show the tight lower bounds for planted clique, together with the reductions of [BR13a, GMZ14], also imply the tight lower bounds for Sparse PCA, as shown in this paper.

4 Our contribution

We give a direct, unconditional lower bound proof for computing Sparse PCA using degree-4 SoS algorithms, showing that they too require $n=\widetilde{\Omega}(k^{2})$ samples to solve the detection problem (Theorem 3.1), which is tight up to polylogarithmic factors when the strength of the signal $\lambda$ is a constant. Indeed the theorem gives a lower bound for every strength $\lambda$, which becomes weaker as $\lambda$ gets larger. Our proof proceeds by constructing the necessary pseudo-moments for the SoS program that achieve too high an objective value (in the jargon of optimization, we prove an “integrality gap” for these programs). As usual in such proofs, there is tension between having the pseudo-moments satisfy the constraints of the program and keeping them positive semidefinite (PSD). Differing from past lower bound proofs, we construct two different PSD moments, each approximately satisfying one sets of constraints in the program and is negligible on the rest. Thus, their sum give PSD moments which approximately satisfy all constraints. We then perturb these moments to satisfy constraints exactly, and show that with high probability over the random data, this perturbation leaves the moments PSD.

We note several features of our lower bound proof which makes the result particularly strong and general. First, it applies not only for the Gaussian distribution, but also for Bernoulli and other distributions. Indeed, we give a set of natural (pseudorandomness) conditions on the sampled data vectors under which the SoS algorithm is “fooled”, and show that these conditions are satisfied with high probability under many similar distributions (possessing strong concentration of measure). Next, our lower bound holds even if the hidden sparse vector is discrete, namely its entries come from the set $\{0,\pm\frac{1}{\sqrt{k}}\}$. We also extend the lower bound for the detection problem to apply also to the estimation problem, in the regime when the ambient dimension is linear in the number of samples, namely $n\leq p\leq Bn$ for constant $B$ (see Theorem 3.2).

Organization: Section 2 provides more backgrounds of sparse PCA and SoS algorithms. Then we state our main results in Section 3. In Section 4, we design the pseudo-moments and state their properties and then in Section 5 we prove our main theorems using these moments. Section 6 and 7 contain the analysis of the moments. Section 8 lists the tools that we heavily used for proving concentration inequalities in the analysis. Finally we conclude with a discussion of further directions of study in Section 9.

Formal description of the model and problem

1 Sparse PCA estimation and detection problems

It is also interesting to also consider the sparse component detection problem [BR13b, BR13a], which is the decision problem of distinguishing from random samples the following two distributions

$H_{0}$: data $X^{j}=\xi^{j}$ is purely random

$H_{v}$: data $X^{j}=\xi^{j}+\sqrt{\lambda}g^{j}v$ contains a hidden sparse signal with strength $\lambda$.

Rigollet [MR14] observed that a polynomial time algorithm for estimation version of sparse PCA with constant error implies that an algorithm for the detection problem with twice number of the samples. Thus, for polynomial time lower bounds, it suffices to consider the detection problem.

We will use $X$ as a shorthand for the $p\times n$ matrix $\left[X^{1},\dots,X^{n}\right]$. We denote the rows of $X$ as $X_{1}^{T},\dots,X_{p}^{T}$, therefore $X_{i}$’s are $n$-dimensional column vectors. The empirical covariance matrix is defined as $\hat{\Sigma}=\frac{1}{n}XX^{T}$.

2 Statistically optimal estimator/detector

It is well known that the following non-convex program achieves optimal statistical minimax rate for the estimation problem and the optimal sample complexity for the detection problem. Note that we scale the variables $x$ up by a factor of $\sqrt{k}$ for simplicity (the hidden vector now has entries from $\{0,\pm 1\}$).

The non-convex program (2.2) statistically optimally solves the sparse PCA problem when $n\geq Ck/\lambda^{2}\log p$ for some sufficiently large $C$. Namely, the following hold with high probability. If $X$ is generated from $H_{v}$, then optimal solution $x_{\textrm{opt}}$ of program (2.2) satisfies $\|\frac{1}{k}\cdot x_{\textrm{opt}}x_{\textrm{opt}}^{T}-vv^{T}\|\leq\frac{1}{3}$, and the objective value $\lambda_{\max}^{k}(\hat{\Sigma})$ is at least $1+\frac{2\lambda}{3}$. On the other hand, if $X$ is generated from null hypothesis $H_{0}$, then $\lambda_{\max}^{k}(\hat{\Sigma})$ is at most $1+\frac{\lambda}{3}$ .

Therefore, for the detection problem, once can simply use the test $\lambda_{\max}^{k}(\hat{\Sigma})>1+\frac{\lambda}{2}$ to distinguish the case of $H_{0}$ and $H_{v}$, with $n=\widetilde{\Omega}(k/\lambda^{2})$ samples. However, this test is highly inefficient, as the best known ways for computing $\lambda_{\max}^{k}(\hat{\Sigma})$ take exponential time! We now turn to consider efficient ways of solving this problem.

3 Sum of Squares (Lasserre) Relaxations

Here we will only briefly introduce the basic ideas of Sum-of-Squares (Lasserre) relaxation that will be used for this paper. We refer readers to the extensive [Las15, Lau09, BS14] for detailed discussions of sum of squares algorithms and proofs and their applications to algorithm design.

For a mutli-set $S\subset[n]$, we use $x^{S}$ to denote the monomial $\prod_{i\in S}x_{i}$. Since $M$ is a linear operator, it can be clearly described by all the values of $M$ on the monomial of degree $d$, that is, all the values of $M(x^{S})$ for mutli-set $S$ of size at most $d$ uniquely determines $M$. Moreover, the nonnegativity constraint $M(p(x)^{2})\geq 0$ is equivalent to the positive semidefiniteness of the matrix-form (as defined below), and therefore the set of all pseudo-moments is convex.

For an even integer $d$ and any degree-$d$ pseudo-moments $M$, we define the matrix-form of $M$ as the trivial way of viewing all the values of $M$ on monomials as a matrix: we use $\textup{mat}(M)$ to denote the matrix that is indexed by multi-subset $S$ of $[n]$ with size at most $d/2$, and $\textup{mat}(M)_{S,T}=M(x^{S}x^{T})$.

Given polynomials $p(x)$ and $q_{1}(x),\dots,q_{m}(x)$ of degree at most $d$, and a polynomial program,

Note that (2.6) is a valid relaxation because for any solution $x_{*}$ of (2.5), if we define $M(x^{S})$ to be $M(x^{S})=x_{*}^{S}$, then $M$ satisfies all the constraints and the objective value is $p(x_{*})$. Therefore it is guaranteed that the optimal value of (2.6) is always larger than that of (2.5).

Finally, the key point is that this program can be solved efficiently, in polynomial time in its size, namely in time $n^{O(d)}$. As $d$ grows, the constraints added make the “pseudo-distribution” defined by the moments closer and closer to an actual distribution, thus providing a tighter relaxation, at the cost of a larger running time to solve it.

In the next section we apply this relaxation to the Sparse PCA problem and state our results.

Main Results

To exploit the sum of squares relaxation framework as described in Section 2.3], we first convert the statistically optimal estimator/detector (2.2) into the “polynomial” program version below.

Now we are ready to apply the sum-of-squares relaxation scheme described in Section 2.3) to the polynomial program above as . For degree-4 relaxation we obtain the following semidefinite program $\textrm{SoS}_{4}(\hat{\Sigma})$, which we view as an algorithm for both detection and estimation problems. Note that the same objective function, with only the three constraints (C1), (C2), (C6) gives the degree-2 relaxation, which is precisely the standard SDP relaxation of Sparse PCA studied in [AW09, BR13b, KNV15]. So clearly $\textrm{SoS}_{4}(\hat{\Sigma})$ subsumes the SDP relaxation.

Before stating the lower bounds for both detection and estimation in the next two subsections, we comment on the choices made for the outputs of the algorithm in both, as clearly other choices can be made that would be interesting to investigate. For detection, we pick the natural threshold $(1+\frac{1}{2}\lambda)k$ from the statistically optimal detection algorithm of Section 2.2. Our lower bound of the objective under $H_{0}$ is actually a large constant multiple of $\lambda k$, so we could have taken a higher threshold. To analyze even higher ones would require analyzing the behavior of $\textrm{SoS}_{4}$ under the (planted) alternative distribution $H_{v}$. For estimation we output the maximizer $M_{2}^{*}$ of the objective function, and prove that it is not too correlated with the rank-1 matrix $vv^{T}$ in the planted distribution $H_{v}$. This suggest, but does not prove, that the leading eigenvector of $M_{2}^{*}$ (which is a natural estimator for $v$) is not too correlated with $v$. We finally note that Rigollet’s efficient reduction from detection to estimation is not in the SoS framework, and so our detection lower bound does not automatically imply the one for estimation.

For the detection problem, we prove that $\textrm{SoS}_{4}(\hat{\Sigma})$ gives a large objective value on null hypothesis $H_{0}$.

There exists absolute constant $C$ and $r$ such that for $1\leq\lambda<\min\{k^{1/4},\sqrt{n}\}$ and any $p\geq C\lambda n$, $k\geq C\lambda^{7/6}\sqrt{n}\log^{r}p$, the following holds. When the data $X$ is drawn from the null hypothesis $H_{0}$, then with high probability ($1-p^{-10}$), the objective value of degree-4 sum of squares relaxation $\textrm{SoS}_{4}(\hat{\Sigma})$ is at least $10\lambda k$. Consequently, Algorithm 1 can’t solve the detection problem.

To parse the theorem and to understand its consequence, consider first the case when $\lambda$ is a constant (which is also arguably the most interesting regime). Then the theorem says that when we have only $n\ll k^{2}$ samples, degree-4 SoS relaxation $\textrm{SoS}_{4}$ still overfits heavily to the randomness of the data $X$ under the null hypothesis $H_{0}$. Therefore, using $\textrm{SoS}_{4}(\hat{\Sigma})>(1+\frac{\lambda}{2})k$ (or even $10\lambda k$) as a threshold will fail with high probability to distinguish $H_{0}$ and $H_{v}$.

We note that for constant $\lambda$ our result is essentially tight in terms of the dependencies between $n,k,p$. The condition $p=\widetilde{\Omega}(n)$ is necessary since otherwise when $p=o(n)$, even without the sum of squares relaxation, the objective value is controlled by $(1+o(1))k$ since $\hat{\Sigma}$ has maximum eigenvalue $1+o(1)$ in this regime. Furthermore, as mentioned in the introduction, $k\geq\widetilde{\Omega}(\sqrt{n})$ is also necessary (up to poly-logarithmic factors), since when $n\gg k^{2}$, a simple diagonal thresholding algorithm works for this simple single-spike model.

When $\lambda$ is not considered as a constant, the dependence of the lower bound on $\lambda$ is not optimal, but close. Ideally one could expect that as long as $k\gg\lambda\sqrt{n}$, and $p\geq\lambda n$, the objective value on the null hypothesis is at least $\Omega(\lambda k)$. Tightening the $\lambda^{1/6}$ slack, and possibly extending the range of $\lambda$ are left to future study.

2 Lower bounds for the estimation problem

For estimation problem, we prove that $M_{2}^{*}$ output by Algorithm 1 is not too correlated with the desired rank-1 matrix $vv^{T}$.

For any constant $B$ there exists absolute constants $C$ and $r$ such that for $\lambda\leq B/2$, $Bn\geq p\geq 2\lambda n$ and $o(p)\geq k\geq C\sqrt{n}\log^{r}p$, suppose the data $X$ is drawn hypothesis $H_{v}$ (model (2.1)), then with high probability $(1-p^{-10}$) over the randomness of the data, Algorithm 1 will output $M_{2}^{*}$ such that $\|\frac{1}{k}\cdot M_{2}^{*}-vv^{T}\|\geq 1/5$.

We observe that the result is of the same nature (and arguably near-optimal for estimation problem) as [KNV15] achieve the for degree-2 SoS relaxation. The proof follows simply from combining our detection lower bound Theorem 3.1 and arguments similar to [KNV15]. Finally we address a threshold-like behavior of the estimation error. Note that while our Theorem proves that $n=\widetilde{\Omega}(k^{2})$ samples is necessary for efficient algorithms to get even constant estimation error, it is known [YZ13, Ma13, WLL14] that slightly more samples, $n=\widetilde{O}(k^{2})$, can already achieve in polynomial time a much smaller (and optimal) estimation error, namely $O(\sqrt{(k\log p)/n})$.

Design of Pseudo-moments

We start with a sketch of our approach to the design of the moments $M$ at a very high level, highlighting aspects of their design which are different than in previous lower bounds. First, there are some natural choices to make. We define the degree-2 moments $\widetilde{M}$ from the input as the empirical covariance matrix, as was done in the proof of the SDP lower bound. This already gives a large objective value (see Lemma 4.2). We also define taking odd moments (degree 1 and 3) to be 0. The difficult part is designing the degree-4 moments consistently with the constraints and $\widetilde{M}$. We do this in stages, first approximating the constraints (indeed even $\widetilde{M}$ only approximately satisfies, in a way we will specify in Section 4.1, constraints (C1) and (C2)) and later in Section 4.2 correcting the moments to satisfy the constraints precisely. Moreover, we separately use different 4-moments for different constraints and then combine them, as follows. We define two different degree-4 PSD moments $P$ and $Q$ such that (with high probability) $P$ almost satisfies constraints (C3), (C5) and (C6), and negligible for constraint (C4) (see Lemma 4.4), whereas $Q$ almost satisfies constraints (C5), (C4) and (C6), and negligible for (C3) (Lemma 4.5). Therefore taking the sum $P+Q$ will almost satisfy all the constraints (Lemma 4.6), which completes the design of the approximate moments. Finally we “locally” adjust $P+Q$ so that the resulting moments $M$ exactly satisfy all the constraints (Theorem 4.7), and remain PSD with high probability.

All moments will be defined from the data matrix $X$, to which we first apply a simple pre-processing step: we scale all its rows to have square norm $n$ (around which they are concentrated). We abuse notation and call the scaled matrix $X$ as well. Note that when the noise model in the null hypothesis $H_{0}$ is Bernoulli, namely the entries of $X$ are chosen as unbiased independent $\pm 1$ variables, the rows are automatically scaled, which motivates our abuse of notation. We suggest that the reader thinks of this distribution, even though the proof works for a much wider class of distributions.

The properties above of our moments will be proved under the assumption that the scaled matrix $X$ satisfies the “pseudo-randomness” condition below. This set-up allows us to encapsulate what we really need the data to satisfy, and thus prove our lower bound not only for Gaussian or Bernoulli noise, but actually for a larger family containing both. Namely, we later prove in Section 7, via a series of concentration inequalities, that when data is drawn from null hypothesis $H_{0}$, its scaling $X$ satisfies the pseudorandomness condition with very high probability under all these noise models. Note that this condition is actually a sequence of statements about deviation from the mean of various polynomials in the data - these will become natural once we define our moments.

Our constructions of the moments will only require the following pseudorandom conditions about the (scaled) data matrix $X$,

In this section, we design a pseudo-moments $\widetilde{M}$ that approximately satisfies the all the constraints. Then in the next subsection we will locally adjust it to obtain one that exactly satisfies all of the constraints.

where $\gamma$ is a constant that to be tuned later according to the signal strength $\lambda$. Note that by design $\textup{mat}(\widetilde{M})$ is a PSD matrix. We can check straightforwardly that $\widetilde{M}$ satisfies constraint (C2) and gives a large objective value (Obj).

There exists constant $C$ such that for $p\geq\gamma n$ and $k\geq C\gamma\sqrt{n}\log p$, suppose $X$ satisfies Condition 4.1, then $\widetilde{M}$ is a valid degree-2 pseudo-moments and satisfies the sparsity constraint (C2).

Moreover, we also have $\widetilde{M}(x_{i}^{2})=\frac{\gamma kn}{p^{2}}\leq\frac{k}{p}$, and $\widetilde{M}(x_{i}x_{j})\leq\widetilde{O}(\frac{\gamma k\sqrt{n}}{p^{2}})$.

The proof follows simple calculation and concentration inequality. Since $\|X_{i}\|^{2}=n$ for all $i$ and with high probability over the randomness of $X$, for all $i\neq j$, $|\langle X_{i},X_{j}\rangle|\leq\widetilde{O}(\sqrt{n})$, we obtain that $\widetilde{M}(x_{i}^{2})=\frac{\gamma kn}{p^{2}}\leq\frac{k}{p}$, and $\widetilde{M}(x_{i}x_{j})\leq\widetilde{O}(\frac{\gamma k\sqrt{n}}{p^{2}})$. Then to verify equation (4.2), we have

when $k\gg\gamma\sqrt{n}$. Finally, we can verify the objective value is large

where we use the fact that $\|XX^{T}\|_{F}^{2}\geq(1-o(1))p^{2}n$ (see property (P7) in Condition 4.1). ∎

Note that $\widetilde{M}$ doesn’t satisfies constraint (C1) exactly. However, we could simply fix this by defining $M^{\prime}(x_{i}x_{j})=\widetilde{M}(x_{i}x_{j})$ for all $i\neq j$ and $M^{\prime}(x_{i}^{2})=k/p$. However, note that we will use a perturbation of $M^{\prime}$ in our final design in Section 4.2 so that it is consistent with the degree-4 moments.

There exists absolute constant $C$ such that for $p\geq\gamma n$ and $k\geq C\gamma\sqrt{n}\log p$, there exists a degree-2 pseudo-moments $M^{\prime}$ that satisfies constraints (C1), (C2) and give objective value at least $(1-o(1))\gamma k$.

Now we define a degree-4 pseudo-moment that approximately satisfies all the constraints in $\textrm{SoS}_{4}(\hat{\Sigma})$ and give a large objective value. We keep the current (approximate) design $\widetilde{M}$ for degree-2 moments, since the degree-2 moments defined in previous section seems to be nearly optimal and enjoys many good properties. Then we define $\widetilde{M}(S)=0$ for any multi-set $S$ of size 3, because apparently degree-3 moments don’t play any role the semidefinite relaxation.

The main difficulty is to define $\widetilde{M}(S)$ for $S$ of size 4. Here we have three constraints (C3), (C4), and (C5), and the PSDness constraint that implicitly compete with each other. We took the following approach. We let $\widetilde{M}$ be a sum of two matrices matrix $P$ and $Q$. We ensure that $P$ “almost” (as will be specified later) satisfies (C3) and (C5), and is negligible for constraints C4. In turn $Q$ is negligible for constraints (C3) and “almost” satisfies constraint (C4) and (C5). Therefore $P+Q$ will “almost” satisfies constraints (C3)) and (C4)), and satisfy the sparsity constraint (C5). Moreover, $P$ and $Q$ will be PSD by definition. Concretely, we define

We note that $P$ and $Q$ are well defined pseudo-moments because they are invariant to the permutation of indices and naturally PSD. To see the PSDness, note that $P$ is a sum of $p$ rank-1 PSD matrices. Moreover, $Q$ is also PSD: the part that correpsonds to $\langle X_{s},X_{t}\rangle\langle X_{i},X_{j}\rangle$ is simply a rank-1 PSD matrix; $\langle X_{i},X_{t}\rangle\langle X_{s},X_{j}\rangle$ can be written as $\langle X_{t}\otimes X_{s},X_{i}\otimes X_{j}\rangle$ and therefore it also contributes a PSD matrix to $Q$. Similarly, $\langle X_{j},X_{t}\rangle\langle X_{s},X_{i}\rangle$ can be written as $\langle X_{s}\otimes X_{t},X_{i}\otimes X_{j}\rangle$, and it also contributes a PSD matrix.

In the next two lemmas (one for $P$ and one for $Q$), we formalize the intuition above by showing that, the deviation from $P$ and $Q$ exactly satisfying the constraints is captured by error matrices $\mathcal{E},\mathcal{F},\mathcal{G}$. We bound the magnitude of these error matrices and establish the PSDness of some of them so that later we can fix them for the exact satisfaction of the constraints.

There exists some absolute constant $C$ and $r$ such that for $1\leq\gamma\leq\min\{k^{1/4},\sqrt{n}\}$, $1\leq\gamma\leq n$, $p=1.1\gamma n$, and $k\geq C\cdot\gamma^{7/6}\sqrt{n}\log^{r}p$, suppose $X$ satisfies pseudorandomness condition 4.1, then $P$ almost satisfies constraint (C3)and (C5), naturally satisfies PSD constraint (C6), and is negligible for constraint (C4) in the sense that

where $\mathcal{F}$ and $\mathcal{E}$ are $p\times p$ matrices that satisfy

$0\leq\mathcal{F}_{ii}\leq\widetilde{O}\left(\frac{\gamma k}{pn}\right)$, $|\mathcal{F}_{ij}|\leq\widetilde{O}\left(\frac{\gamma k}{pn^{1.5}}\right)$ for any $i$ and $j\neq i$.

$\mathcal{E}$ is PSD with $|\mathcal{E}_{ss}|\leq\widetilde{O}\left(\frac{\gamma k}{n}\right)$, and $|\mathcal{E}_{st}|\leq\widetilde{O}(\frac{\gamma k}{n\sqrt{n}})$ for any $s\neq t$.

There exists some absolute constant $C$ and $r$ such that for $1\leq\gamma\leq n$, $p=1.1\gamma n$ and $k\geq C\cdot\gamma\sqrt{n}\log^{r}p$, suppose $X$ satisfies pseudorandomness condition 4.1, then $Q$ is negligible for constraint (C3)) and almost satisfies constraint (C4) and (C5) in the sense that,

where $\mathcal{G}$ is a $p\times p$ PSD matrix $|\mathcal{G}_{ss}|\leq\widetilde{O}\left(\frac{\gamma k^{2}}{p^{2}}\right)$ and $|\mathcal{G}_{st}|\leq\widetilde{O}\left(\frac{\gamma k^{2}}{p^{2}\sqrt{n}}\right)$ for any $s\neq t$.

Now we are ready to prove that $\widetilde{M}=P+Q$ almost satisfies all other constraints (C1)- (C6) approximately.

Define $\widetilde{M}(x_{i}x_{j}x_{s}x_{t})=P(x_{i}x_{j}x_{s}x_{t})+Q(x_{i}x_{j}x_{s}x_{t})$ for all $i,j,s,t\in[p]$, then we have under the condition of Lemma 4.4,

where $\mathcal{F}^{\prime}$ and $\mathcal{E}^{\prime}$ are $p\times p$ matrices that satisfy

$|\mathcal{F}_{ii}^{\prime}|\leq\widetilde{O}\left(\frac{\gamma k^{2}n}{p^{3}}\right)$ and $|\mathcal{F}^{\prime}_{ij}|\leq\widetilde{O}\left(\frac{\gamma k^{2}\sqrt{n}}{p^{3}}\right)$ for all $i\neq j$.

$\mathcal{E}^{\prime}$ is a PSD matrix with $\mathcal{E}^{\prime}_{ss}\leq\widetilde{O}\left(\frac{\gamma k}{n}\right)$ and $|\mathcal{E}^{\prime}_{st}|\leq\widetilde{O}(\frac{\gamma k}{n\sqrt{n}})$ for $s\neq t$.

Note that by definition of $\widetilde{M}$ and Lemma 4.4 and Lemma 4.5, we have $\mathcal{F}^{\prime}_{ij}=\mathcal{F}_{ij}+\frac{3k}{p}\widetilde{M}(x_{i}x_{j})$ and $\mathcal{E}^{\prime}=\mathcal{E}+\mathcal{G}$. The bound for $\mathcal{F}^{\prime}$ follows the bound for $\mathcal{F}$ and the facts that $\widetilde{M}(x_{i}^{2})=\frac{\gamma kn}{p^{2}}$ and $|\widetilde{M}(x_{i}x_{j})|\leq\widetilde{O}\left(\frac{\gamma k\sqrt{n}}{p^{2}}\right)$. The PSDness of $\mathcal{E}^{\prime}$ and the bounds for it follows straightforwardly from those of $\mathcal{E}$ and $\mathcal{G}$. Equation (4.11) follows equation (4.4) and equation (4.8). ∎

2 Exact Pseudo-moments

Note that $\widetilde{M}$ only satisfies the constraints approximately up to some additive errors (which are carefully bounded for the purpose of the next theorem). We fix this issue by defining the actual pseudo-moments $M$ based (on a carefully chosen) local adjustment of $\widetilde{M}$. Concretely, we define $M(1)=1$ and for all add degree monomial $x^{\alpha}$, $M(x^{\alpha})=0$. For distinct $i,j,s,t$, we define $M(x_{i}x_{j}x_{s}x_{t})\triangleq\widetilde{M}(x_{i}x_{j}x_{s}x_{t})$ and $M(x_{i}^{2}x_{s}x_{t})\triangleq\widetilde{M}(x_{i}^{2}x_{s}x_{t})$. For distinct $s,t$, we define

and $M(x_{s}^{2}x_{t}^{2})\triangleq\widetilde{M}(x_{s}^{2}x_{s}^{2})+\delta$ where $\delta$ a constant (will be proved to be nonnegative) such that

Therefore we can see by construction, it is almost obvious that $M$ satisfies all the linear constraints (C1), (C3), (C4) exactly. Moreover, since $\mathcal{E}^{\prime}$ and $\mathcal{F}^{\prime}$ are small error matrices, most of the entries $M(x_{i}x_{j}x_{s}x_{t})$ are equal or close to $\widetilde{M}(x_{i}x_{j}x_{s}x_{t})$. Note that $\widetilde{M}$ satisfies the rest of constraints (C2), (C5) and (C6) (even with some slackness). We will prove that the difference between $M$ and $\widetilde{M}$ is small enough so that these constraints are still satisfied by $M$.

Under the condition of Lemma 4.4, suppose $X$ satisfies pseudorandomness condition 4.1, then the pseudo-moments $M$ defined above satisfies all the constraint (C1)-(C6) of the semidefinite programming and has objective value larger than $(1-o(1))\gamma k$.

We prove that $M$ satisfies all the constraints in an order that is most convenient for the proof, and check the objective value at the end.

Constraint (C3): This is satisfied by the definition of $M$.

Constraint (C4): By the definition, we can see that $M(x_{s}^{3}x_{t})$ is also a perturbation of $\widetilde{M}(x_{s}^{3}x_{t})$:

where the second equality uses definition (4.12) and the third uses equation (4.9), and the fourth uses (4.10) and the last equality uses the definition (4.12) again.

Moreover, for the case when $s=t$, we have that

where we used the definition (4.14) of $M(x_{s}^{4})$ and $M(x_{s}^{2})$. Therefore we verified that $M$ satisfies constraint (C4).

Constraint (C1): Using equation (4.13) and (4.14), we have

Next we check the PSDness of matrix $\textup{mat}(M)$. Note that $\textup{mat}(M)$ is indexed by all the mutli subset of $[p]$ of size at most 2, and it consists of 3 blocks $\textup{mat}(M)=\textrm{blkdiag}(M_{4},M_{2},M_{0})$, where

Therefore it suffices to check that $M_{0}$, $M_{2}$ and $M_{4}$ are all PSD. $M_{0}$ is trivially PSD. We can write $M_{2}$ in the following form

where $\Delta=M_{2}-\left(\widetilde{M}(x_{s}x_{t})\right)_{s,t\in[p]}$. By equation (4.12), we have that for $s\neq t$, $\Delta_{st}=\frac{1}{k-2}\left(\mathcal{E}^{\prime}_{st}-2\mathcal{F}^{\prime}_{st}\right)$ for all $s\neq t$. Moreover, by definition of $M(x_{s}^{2})$ and $M(x_{s}^{2}x_{t}^{2})$, we have that

where second line uses equation (4.10) and the third line uses (4.9), and therefore $\Delta_{ss}=\frac{p-1}{k-1}\cdot\delta+\frac{1}{k-1}\left(\mathcal{E}_{ss}^{\prime}-\mathcal{F}_{ss}^{\prime}\right)$. We extract the PSD matrix $\frac{1}{k-2}\cdot\mathcal{E}^{\prime}$ form $\Delta$ and obtain $\Delta^{\prime}=\Delta-\frac{1}{k-2}\cdot\mathcal{E}^{\prime}$. Then by this definition, $\Delta^{\prime}_{ss}=\frac{p-1}{k-1}\cdot\delta+\frac{1}{k-1}\left(\mathcal{E}_{ss}^{\prime}-\mathcal{F}_{ss}^{\prime}\right)-\frac{1}{k-2}\mathcal{E}_{ss}^{\prime}$, and $\Delta^{\prime}_{st}=-\frac{2}{k-2}\mathcal{F}^{\prime}_{st}$. We use Gershgorin Circle Theorem to establish the PSDness of $\Delta^{\prime}$. By Lemma 4.6, we have $|\mathcal{F}_{ij}|\leq\widetilde{O}\left(\frac{\gamma k^{2}\sqrt{n}}{p^{3}}\right)$ Therefore

where we used the fact that $\sqrt{n}/p=o(1)$ which follows form $p=1.1\gamma n$ and $\gamma\leq\sqrt{n}$.

Using equation (4.16) and constrain (C1) we have that

It follows that $\delta\geq(1-o(1))\cdot\frac{k(k-1)}{12p(p-1)}$. Therefore we obtain that $\Delta_{ii}^{\prime}=\frac{p-1}{k-1}\cdot\delta+\frac{1}{k-1}\left(\mathcal{E}_{ss}^{\prime}-\mathcal{F}_{ss}^{\prime}\right)-\frac{1}{k-2}\mathcal{E}_{ss}^{\prime}\geq\frac{1}{12}(1-o(1))\frac{k}{p}-\widetilde{O}(\frac{\gamma}{n})-\widetilde{O}\left(\frac{\gamma kn}{p^{3}}\right)=\frac{1}{12}(1-o(1))\frac{k}{p}$. Therefore we obtain $\Delta_{ii}^{\prime}\geq\sum_{j:j\neq i}|\Delta_{ij}^{\prime}|$ and by Gershgorin Circle Theorem $\Delta^{\prime}$ is PSD.

Now we examine $M_{4}$. we write $M_{4}$ as

where $\Gamma=M_{4}-\left(\textup{mat}(P)+\textup{mat}(Q)\right)$. One can observe that $\Gamma$ has only non-zero entries of the form

where the last equality uses equation (4.15).

Now we are ready to prove PSDness of $\Gamma$. We further decompose $\Gamma$ as $\Gamma=\Gamma^{\prime}+\textrm{blkdiag}(\Lambda^{\prime},0)$ where $\Lambda^{\prime}$ is the $p\times p$ matrix with $\Lambda^{\prime}=\delta\mathbf{1}\mathbf{1}^{T}$ $\Lambda^{\prime}$ is index by $ii$, $i=1,\dots,p$. Note that $\Lambda^{\prime}$ is a PSD matrix and therefore it suffices to prove that $\Gamma^{\prime}=\Gamma-\textrm{blkdiag}(\Lambda^{\prime},0)$ is a PSD matrix.

Note that $\Gamma^{\prime}$ has $ij$-th column the same as $ji$-th column, and therefore it’s only of rank at most $p+p(p-1)/2$. We define $\Gamma^{\prime\prime}$ be the $p+p(p-1)/2$ by $p+p(p-1)/2$ submatrix of $\Gamma^{\prime}$,that is indexed by subsets $(i,i)$ for $i\in[p]$ and $(i,j)$ for $i<j$. Therefore it suffices to prove that $\Gamma^{\prime\prime}$ is PSD. We prove it using Gershgorin Circle Theorem.

Note that by equation (4.19), we have that $\Gamma_{ii,ii}^{\prime\prime}=\Gamma_{ii,ii}^{\prime}-\Lambda_{ii,ii}^{\prime}=\frac{(p-k)}{k-1}\cdot\delta+\frac{1}{k-1}\mathcal{E}^{\prime}_{ii}-\frac{k}{k-1}\mathcal{F}_{ii}$. Therefore by the lower bound for $\delta$ and Lemma 4.6, we obtain, $\Gamma_{ii,ii}^{\prime\prime}\geq(1-o(1))\frac{\epsilon k}{p}$. Moreover, $\Gamma_{ii,ij}^{\prime\prime}=\Gamma_{ii,ij}=\frac{\mathcal{E}^{\prime}_{st}}{k-2}-\frac{k}{k-2}\mathcal{F}_{st}$ and therefore $|\Gamma^{\prime\prime}_{ii,ij}|\leq|\frac{\mathcal{E}^{\prime}_{st}}{k-2}|+|\frac{k}{k-2}\mathcal{F}_{st}|\leq\widetilde{O}(\frac{\gamma}{n^{1.5}})+\widetilde{O}\left(\frac{\gamma k^{2}\sqrt{n}}{p^{3}}\right)\leq\widetilde{O}(\frac{\gamma}{n^{1.5}}).$ Furthermore, for $i<j$, $\Gamma^{\prime\prime}_{ij,ij}=\Gamma_{ij,ij}=\delta\geq(1-o(1))\frac{\epsilon k^{2}}{p^{2}}$. Finally observe that $\Gamma^{\prime\prime}_{ii,jj}=0$ by definition and all other entries of $\Gamma^{\prime\prime}$ are trivially 0 because the corresponding entries of $\Gamma$ and $\Lambda^{\prime}$ vanish. Therefore we are ready to use a variant of Gershogorin Circle Theorem (Lemma 8.8) to prove the PSDness of $\Gamma^{\prime}$. Taking $\alpha=1/\gamma^{2}$, we have for any $i$,

where we used the fact that $k\gg\gamma\sqrt{n}$ and $\epsilon$ is a constant.

where we used $k\geq\gamma^{4}$ and $k\gg\gamma\sqrt{n}$. Therefore by Lemma 8.8, we obtain that $\Gamma^{\prime\prime}$ is PSD.

Constraint (C2): Using Lemma 4.2 and equation (4.12), we have that

Constraint (C5): Finally, we check that $M$ satisfies the sparsity constraint (C5).

where we used (4.11) and the (trivial) facts that $\Gamma_{ij,st}\leq O(k/p)$ for any $i,j,s,t$ and there are only at most $O(p^{2})$ nonzero entries in $\Gamma$.

Objective value (Obj): Note that by constraint (C1) and Lemma 4.2, we have that $\sum_{i}M(x_{i}^{2})\hat{\Sigma}_{ii}=k\geq\sum_{i}\widetilde{M}(x_{i}^{2})\hat{\Sigma}_{ii}$, then

where in the second inequality we used Lemma 4.2 and the facts that $\hat{\Sigma}_{ij}=\frac{1}{n}\langle X_{i},X_{j}\rangle\leq\widetilde{O}(1/\sqrt{n})$ and $|\mathcal{E}^{\prime}|_{ij}+|\mathcal{F}^{\prime}_{ij}|\leq\widetilde{O}\left(\frac{\gamma}{n^{1.5}}\right)$, and the last line uses the fact taht $\gamma^{4}\leq k$.

Proof of Theorem 3.1 and Theorem 3.2

Now we are ready to prove our main Theorem 3.1. The idea is very simple: we normalize the data matrix $X$ so that the resulting matrix $\bar{X}$ satisfies the the pseudorandomness condition 4.1. Then we apply Theorem 4.7 and obtain a moment matrix which give large objective value with respect to $\bar{X}$. Then we argue that the difference between $\bar{X}$ from $X$ is negligible so that the same moment matrix has also large objective value with respect to $X$.

Using the observation above, we take $p=1.1\gamma n$ with $\gamma=11\lambda$, and we define $\bar{X}$ to matrix obtained by normalizing rows of $X$ to euclidean norm $\sqrt{n}$. Then by Theorem 7.1 it satisfies the pseudorandomenss condition 4.1. Let $\hat{\Sigma}^{\prime}=\frac{1}{n}\bar{X}\bar{X}^{T}$ be the covariance matrix defined by $\bar{X}$. By Theorem 4.7 we have that $\textrm{SoS}_{4}(\hat{\Sigma}^{\prime})\geq(1-o(1))\gamma k\geq 11\lambda k$. Moreover, let $M$ be the moment defined in Theorem 4.7, and $M_{2}$ its restriction to degree-2 moments, that is, $M_{2}=\left(\textup{mat}(M)_{S,T}\right)_{|S|=|T|=1}$. We are going to show that the entry-wise difference between $\hat{\Sigma}$ and $\hat{\Sigma}^{\prime}$ are small enough so that $\langle M_{2},\hat{\Sigma}\rangle$ is close to $\langle M_{2},\hat{\Sigma}^{\prime}\rangle$.

Note that since $\|X_{i}\|^{2}=n\pm\widetilde{O}(\sqrt{n})$, therefore for any $i\neq j$, $\hat{\Sigma}^{\prime}_{ij}=\frac{\hat{\Sigma}_{ij}}{\|X_{i}\|\|X_{j}\|}=\hat{\Sigma}_{ij}\pm\widetilde{O}(\frac{1}{\sqrt{n}})|\hat{\Sigma}|_{ij}=\hat{\Sigma}_{ij}\pm\widetilde{O}(\frac{1}{n})$. For $i=j$, we have similarly that $\hat{\Sigma}^{\prime}_{ii}=\hat{\Sigma}_{ii}\pm\widetilde{O}(\frac{1}{\sqrt{n}})$. We bound the difference between $\langle M_{2},\hat{\Sigma}^{\prime}\rangle$ and $\langle M_{2},\hat{\Sigma}^{\prime}\rangle$ by the sum of the entry-wise differences:

Therefore $\langle M_{2},\hat{\Sigma}\rangle\geq(1-o(1))\gamma k-o(k)=(1-o(1))\gamma k$. Therefore the moment $M$ gives objective value $(1-o(1))\gamma k$ for data $\hat{\Sigma}$, and therefore $\textrm{SoS}_{4}(\hat{\Sigma})\geq(1-o(1))\gamma k\geq 10\lambda k$. ∎

Then we prove that Theorem 3.1 together with the arguments in [KNV15] implies Theorem 3.2. The intuition behind is the following: Suppose $M_{2}^{*}$ is very close to $vv^{T}$, then it is close to rank-1 and its leading eigenvector is close to $\hat{v}$. However, since we prove that the objective value is large (which is true also in the planted vector case), $M_{2}^{*}$ needs to be highly correlated with $\hat{\Sigma}$, which implies its leading eigenvector $\hat{v}$ needs to be correlated with $\hat{\Sigma}$, which in turns implies that $v$ is correlated with $\hat{\Sigma}$. However, it turns out that $v$ is not correlated enough with $\hat{\Sigma}$, which leads to a contradiction.

We first prove that the optimal value of $\textrm{SoS}_{4}(\hat{\Sigma})$ for hypothesis $H_{v}$ is also at least $0.99kp/n$. Suppose $v$ has support $S$ of size $k$. We consider the restriction of linear operator $M$ to the subset $T=[p]\backslash S$, denoted by $M_{T}$. That is, we have that $M_{T}(x^{\alpha})=0$ for any monomial $x^{\alpha}$ that contains a factor $x_{i}$ with $i\in S$, and otherwise $M_{T}(x^{\alpha})=M(x^{\alpha})$. We also consider the data matrix $X_{T}$ obtained by restricting to the rows indexed by $T$. Note that since $X_{T}$ doesn’t contain the signal, and $k\gg\sqrt{n})$, using Theorem 4.7 with $\gamma=(p-k)/(1.01n)$, we have that there exists pseudo-moment $M_{T}^{*}$ which gives objective value $\geq(1-o(1))\gamma k\geq 0.99pk/n$ with respective to covariance matrix $\hat{\Sigma}_{T}=\frac{1}{n}X_{T}X_{T}^{T}$. Note that by Proposition 5.1, $\textrm{SoS}_{4}(\hat{\Sigma})\geq\textrm{SoS}_{4}(\hat{\Sigma}_{T})$ and therefore we obtain that under hypothesis $H_{v}$, with high probability, $\textrm{SoS}_{4}(\hat{\Sigma})\geq 0.99kp/n$.

Now suppose $M^{*}$ is the maximizer of $\textrm{SoS}_{4}(\hat{\Sigma})$, and $M_{2}^{*}=\left(M^{*}(x_{i}x_{j})\right)_{i,j\in[p]}$. For the sake of contradiction, we assume that $\|\frac{1}{k}M_{2}^{*}-vv^{T}\|\leq 1/5$. We first show that this implies that $M_{2}^{*}$ has an eigenvector $\hat{v}$ that is close to $v$ and its eigenvalue is large. Indeed we have $\|\frac{1}{k}M_{2}\|\geq\|vv^{T}\|-1/5=4/5$. Therefore the top eigenvector of $\frac{1}{k}M_{2}^{*}$ has eigenvalue larger than $4/5$. Then we can decompose the difference between $\frac{1}{k}\cdot M_{2}^{*}$ and $vv^{T}$ into $\frac{1}{k}\cdot M_{2}^{*}-vv^{T}=\frac{4}{5}\cdot\left(\hat{v}\hat{v}^{T}-vv^{T}\right)+\left(\left(\frac{1}{k}M_{2}^{*}-\frac{4}{5}\hat{v}\hat{v}^{T}\right)-\frac{1}{5}vv^{T}\right)$. Note that since $\left(\frac{1}{k}M_{2}^{*}-\frac{4}{5}\hat{v}\hat{v}^{T}\right)$ is a PSD matrix with eigenvalue at most $1/5$, we have $\|\left(\left(\frac{1}{k}M_{2}^{*}-\frac{4}{5}\hat{v}\hat{v}^{T}\right)-\frac{1}{5}vv^{T}\right)\|\leq 2/5$ by triangle inequality. Then by triangle inequality and our assumption again we obtain that

Therefore we obtain that $\|vv^{T}-\hat{v}\hat{v}^{T}\|\leq 3/5$ and therefore $\|vv^{T}-\hat{v}\hat{v}^{T}\|_{F}^{2}\leq 2\|vv^{T}-\hat{v}\hat{v}^{T}\|^{2}\leq 1$. It follow that $|\langle v,\hat{v}\rangle|^{2}=1-\frac{1}{2}\|vv^{T}-\hat{v}\hat{v}^{T}\|_{F}^{2}\geq 1/2$.

Next we are going to show that it is impossible for $M_{2}^{*}$ to have an eigenvector that is close to $v$ with a large eigenvalue and therefore we will get a contradiction. Let $\hat{v}=\alpha v+\beta s$ where $s$ is orthogonal to $v$ and $\alpha^{2}+\beta^{2}=1$ and $\alpha\geq\sqrt{1/2}$, and $\beta\leq\sqrt{1/2}$. Then using triangle inequality we have that $\|\hat{v}\|_{\hat{\Sigma}}\leq\|\alpha v\|_{\hat{\Sigma}}+\|\beta s\|_{\hat{\Sigma}}\leq\sqrt{O(\lambda)\alpha}+\sqrt{\|\hat{\Sigma}\|\beta}$. Proposition 5.3 of [KNV15] implies that for sufficiently large $C$ and $\lambda\geq 1$, when $p/n\geq C\lambda$, $\|\hat{\Sigma}\|\leq 1.01p/n$. Therefore under our assumption we have that $\|\hat{\Sigma}\|\leq 1.01p/n$. It follows $\beta\leq\sqrt{1/2}$ that $\|\hat{v}\|_{\hat{\Sigma}}\leq\sqrt{O(\lambda)\alpha}+\sqrt{\beta}\cdot\sqrt{p/n}\leq\sqrt{O(\lambda)}+\sqrt{p/2n}$. Therefore, we have that

where in the third line we used the fact that $\|\hat{v}\|_{\hat{\Sigma}}\leq\sqrt{O(\lambda)}+\sqrt{p/2n}$, and the last line we used $\|\hat{\Sigma}\|\leq 1.01p/n$.Note that this is a contradiction since we assumed that $p/n\geq C\lambda$ for sufficiently large $C$.

Analysis of matrices P𝑃P and Q𝑄Q

In this section we prove Lemma 4.4 and 4.5. They basically follow direct calculation and the pseudorandomness properties of data matrix $X$ listed in Condition 4.1.

Note that since $p=1.1\gamma n$ and $1\leq\gamma\leq n$, we have that $O(n^{2})\geq p\geq n$. We verify equations (4.3), (4.4) and (4.5) and the bounds for $\mathcal{F}$ and $\mathcal{E}$ one by one.

For the case when $i=j$, we verify $P(x_{i}^{4})$ using property (P1) and (P2),

where in the second equality we use equation (P3), and $p\geq n$.

Note that for distinct $i,j,s,t$, by equation (P4), we have

Therefore taking the sum over all distinct $i,j,s,t$ we have

where we used $k\gg\gamma^{7/6}\sqrt{n}$, which implies that $k^{3}\gg\gamma p^{2.5}/n$.

By equation (4.2) and equation (4.3), we have that

where we used the fact that $p\leq n^{2}$ and $k\gg\gamma\sqrt{n}$.

Therefore, combining equation (6.1), (6.2), (6.3), we obtain that

Finally it remains to bound $\mathcal{E}$. Note that $\mathcal{E}$ is a sum of submatrices of $P$ and therefore it is PSD. Moreover,

where the last inequality uses equation (P2). Finally we bound $\mathcal{E}_{st}$ using equation (P6)

Again we verify equation (4.6), (4.7) and (4.8) in order.

Equation (4.6): By definition we have that for any $i,j$,

Equation (4.8): For the sparsity constraint, we note first that for distinct $i,j,s,t$, using property (P2), we have

where we used the fact that $k^{2}\gg=\gg c^{2}n$. We bound other terms as follows:

There are only at most $O(p^{3})$ different choices of $i,j,s,t$ such that $i,j,s,t$ are not distinct, therefore we have

where we used the fact that $k\gg\gamma\sqrt{n}$ and $\gamma\geq 1$.

Combining equation (6.4) and (6.5), we obtain that

Therefore $\mathcal{G}_{st}=\frac{2\gamma k^{2}}{p^{3}n}\sum_{i\in[p]}\langle X_{i},X_{s}\rangle\langle X_{i},X_{t}\rangle$ forms a PSD matrix. Moreover, when $s\neq t$, using equation (P5), we have that

Pseudo-randomness of X𝑋X

In this section, we prove that basically as long as the noise model is subgaussian and has variance 1(which generalizes the standard Bernoulli and Gaussian distributions), after normalizing the rows of the data matrix $X\sim H_{0}$, it satisfies the pseudorandomness condition 4.1.

The proof of the Theorem relies on the following Proposition and Theorem 7.4. The proposition says that $\frac{X_{i}^{T}}{\|X_{i}\|}$ still satisfies good properties like symmetry and that each entries has a subgaussian tail, even though its entries are no longer independent due to normalization. These properties will be encapsulated in the definition of a good random variable following the proposition. Then we prove in Theorem 7.4 that these properties suffice for establishing the pseudorandomness Condition 4.1 with high probability. We will heavily use the $\psi_{\alpha}$-Orlicz norm (denoted $\|\cdot\|_{\psi_{\alpha}}$) of a random variable, defined in Definition 8.1, and its properties, summarized in the next (toolbox) section. Intuitively, $\|\cdot\|_{\psi_{2}}$ norm is a succinct and convenient way to capture the “subgaussianity” of a random variable.

$\||x|_{\infty}\|_{\psi_{2}}\leq\widetilde{O}(1)$

For simplicity, we call a random variable good if it satisfies the five properties listed in the proposition above. Goodness will be invoked in most statements below.

We will show a random matrix $X$ with good rows satisfies the pseudo-randomness Condition 4.1 with high probability.

Suppose independent $n$-dimensional random vectors $X_{1},\dots,X_{p}$ with $p\geq n$ are all good, then $X_{1},\dots,X_{p}$ satisfies the pseudorandomness condition 4.1 with high probability.

The general approach to prove the theorem is just to use the concentration of measure. The only caveat here is that in most of cases, the random variables that we are dealing with are not bounded a.s. so we can’t use Chernoff bound or Bernstein inequality directly. However, though these random variables are not bounded a.s., they typically have a light tail, that is, their $\psi_{\alpha}$ norms can be bounded. Then we are going to apply Theorem 8.4 of Ledoux and Talagrand’s, a extended version of Bernstein inequality with only $\psi_{\alpha}$ norm boundedness required. We will also use other known technical results listed in the toolbox Section 8.

Equation (P1) and (P2) follows the assumptions on $X_{i}$’s and union bound. Equation (P3) is proved in Lemma 7.5 by taking $u=X_{s}$ and $v=X_{t}$ and view the rest of $X_{i}$;s as $Z_{j}$’s in the statement of Lemma 7.5. Equation (P4) is proved in Lemma 7.6, (P5) in Lemma 7.8, (P6) in Lemma 7.10, and equation P7 is proved in Lemma 7.15. ∎

For any good random variable $x$, we have that for fixed $u,v$ with $\|u\|^{2}=\|v\|^{2}=n$ , $|u|_{\infty}\leq\widetilde{O}(1)$, $|v|_{\infty}\leq\widetilde{O}(1)$, and $\langle u,v\rangle\leq\widetilde{O}(\sqrt{n})$,