# Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems

Aaron Potechin University of Chicago<EMAIL_ADDRESS>Supported in part
by NSF grant CCF-2008920. Goutham Rajendran University of Chicago.
<EMAIL_ADDRESS>Supported in part by NSF grant CCF-1816372.

###### Abstract

In this paper, we construct general machinery for proving Sum-of-Squares lower
bounds on certification problems by generalizing the techniques used by
[BHK+16] to prove Sum-of-Squares lower bounds for planted clique. Using this
machinery, we prove degree $n^{\varepsilon}$ Sum-of-Squares lower bounds for
tensor PCA, the Wishart model of sparse PCA, and a variant of planted clique
which we call planted slightly denser subgraph.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries and proof overview
  3. 3 Informal Description of our Machinery
  4. 4 Qualitative bounds for Planted slightly denser subgraph
  5. 5 Qualitative bounds for Tensor PCA
  6. 6 Qualitative bounds for Sparse PCA
  7. 7 Technical Definitions and Theorem Statement
  8. 8 Proof of the Main Theorem
  9. 9 Choosing the functions $B_{norm}(\alpha)$, $B(\gamma)$, $N(\gamma)$, and $c(\alpha)$
  10. 10 Showing Positivity
  11. 11 Planted slightly denser subgraph: Full verification
  12. 12 Tensor PCA: Full verification
  13. 13 Sparse PCA: Full verification
  14. A Proof that the Leftmost and Rightmost Minimum Vertex Separators are Well-defined
  15. B Proofs with Canonical Maps

##  1 Introduction

The Sum-of-Squares (SoS) hierarchy is an optimization technique that harnesses
the power of semidefinite programming to solve optimization tasks. For
polynomial optimization problems, the SoS hierarchy, first independently
investigated by Shor [Sho87], Nesterov [Nes00], Parillo [Par00], Lasserre
[Las01] and Grigoriev [Gri01a, Gri01b], offers a sequence of convex
relaxations parameterized by an integer called the degree of the SoS
hierarchy. As we increase the degree $d$ of the hierarchy, we get
progressively stronger convex relaxations, while being solvable in $n^{O(d)}$
time. This has paved the way for the SoS hierarchy to be a powerful tool in
algorithm design both in the worst case and the average case settings. Indeed,
there has been tremendous success in using the SoS hierarchy to obtain
efficient algorithms for combinatorial optimization problems (e.g., [GW95,
ARV04, GS11, RRS17]) as well as problems stemming from Statistics and Machine
Learning (e.g., [BBH+12, BKS15, HSS15, PS17, KS17]).

On the flip side, some problems have remained intractable beyond a certain
threshold even by considering higher degrees of the SoS hierarchy [BHK+16,
KMOW17, MRX20, GJJ+20]. For example, consider the Planted Clique problem where
we have to distinguish a random graph sampled from the Erdős-Rényi model
$G(n,\frac{1}{2})$ from a random graph which is obtained by first sampling a
graph from $G(n,\frac{1}{2})$ and then planting a clique of size
$n^{\frac{1}{2}-\varepsilon}$ for a small constant $\varepsilon>0$. It was
shown in [BHK+16] that with high probability degree $o(\log n)$ SoS fails to
solve this distinguishing problem.

There are many reasons for why studying lower bounds against the SoS hierarchy
is important. Firstly, since SoS is a generic proof system that captures a
broad class of algorithmic reasoning, SoS lower bounds indicate to the
algorithm designer the intrinsic hardness of the problem and that if they want
to break the algorithmic barrier, they need to search for algorithms that are
not captured by SoS. Secondly, in average case problem settings, standard
complexity theoretic assumptions such as P $\neq$ NP have not been shown to
give insight into the limits of efficient algorithms. Instead, lower bounds
against powerful proof systems such as SoS have served as strong evidence of
hardness [Hop18]. Moreover, for a large class of problems, it’s been shown
that SoS relaxations are the most efficient among all semidefinite programming
relaxations [LRS15]. Thus, understanding the power of the SoS hierarchy on
these problems is an important step towards understanding the approximability
of these problems.

###  1.1 Our Contributions

In this paper, we consider the following general category of problems. Given a
random input, can we certify that it does not contain a given structure?

Some important examples of this kind of problem are as follows.

  1. 1.

Planted clique: Can we certify that a random graph does not have a large
clique?

  2. 2.

Tensor PCA: Given an order $k$ tensor $T$ with random Gaussian entries, can we
certify that there is no unit vector $x$ such that $\langle
T,x\otimes\ldots\otimes x\rangle$ is large?

  3. 3.

Wishart model of sparse PCA: Given an $m\times d$ matrix $S$ with random
Gaussian entries (which corresponds to taking $m$ samples from
$\mathcal{N}(0,I_{d})$), can we certify that there is no $k$-sparse unit
vector $x$ such that $\left\lVert Sx\right\rVert$ is large?

These kinds of problems, known as certification problems, are closely related
to their optimization or estimation variants. A certification algorithm is
required to produce a proof/certificate of a bound that holds for all inputs,
as opposed to most inputs. The Sum-of-Squares hierarchy provides such
certificates, so analyzing SoS paves the way towards understanding the
certification complexity of these problems. We investigate the following
question.

> For certification problems, what are the best bounds that SoS can certify?

In this work, we build general machinery for proving probabilistic Sum of
Squares lower bounds on certification problems. To build our machinery, we
generalize the techniques pioneered by [BHK+16] for proving Sum of Squares
lower bounds for planted clique. We start with the standard framework for
proving probabilistic Sum of Squares lower bounds:

  1. 1.

Construct candidate pseudo-expectation values $\tilde{\mathop{\mathbb{E}}}$
and the corresponding moment matrix $\Lambda$ (see Section 2.1).

  2. 2.

Show that with high probability, $\Lambda\succeq 0$.

For planted clique, [BHK+16] constructed $\tilde{\mathop{\mathbb{E}}}$ and the
corresponding moment matrix $\Lambda$ by introducing the pseudo-calibration
technique (see Section 2.2). They then showed through a careful and highly
technical analysis that with high probability $\Lambda\succeq 0$.

In this paper, by generalizing the techniques used in this analysis, we give
general conditions which are sufficient to show that a candidate moment matrix
$\Lambda$ is positive-semidefinite (PSD) with high probability. These
conditions, which are our main result, are stated informally in Theorem 3.32
and stated formally in Theorem 7.95 and Theorem 7.101.

####  1.1.1 Pseudo-calibration and Our Machinery

A natural way to prove lower bounds on a certification problem is as follows.

  1. 1.

Construct a planted distribution of inputs which has the given structure.

  2. 2.

Show that we cannot distinguish between the random and planted distributions
and thus cannot certify that a random input does not have the given structure.

Based on this idea, the pseudo-calibration technique introduced by [BHK+16]
constructs candidate pseudo-expectation values $\tilde{\mathop{\mathbb{E}}}$
so that as far as low degree tests are concerned,
$\tilde{\mathop{\mathbb{E}}}$ for the random distribution mimics the behavior
of the given structure for the planted distribution (for details, see Section
2.2). This gives a candidate moment matrix $\Lambda$ which we can then analyze
with our machinery. Indeed, this is how we prove our SoS lower bounds for
tensor PCA, the Wishart model of sparse PCA, and a variant of planted clique
which we call planted slightly denser subgraph. That said, our machinery does
not require that the candidate moment matrix $\Lambda$ be obtained via pseudo-
calibration.

####  1.1.2 Results on Tensor PCA, Sparse PCA, and Planted Slightly Denser
Subgraph

We now describe the planted distributions we use to show our SoS lower bounds
for planted slightly denser subgraph, tensor PCA, and the the Wishart model of
sparse PCA. We also state the random distributions for completeness and for
contrast. We then state our results.

##### Planted slightly denser subgraph

We use the following distributions.

  * []

  * -

Random distribution: Sample $G$ from $G(n,\frac{1}{2})$

  * -

Planted distribution: Let $k$ be an integer and let $p>\frac{1}{2}$. Sample a
graph $G^{\prime}$ from $G(n,\frac{1}{2})$. Choose a random subset $S$ of the
vertices, where each vertex is picked independently with probability
$\frac{k}{n}$. For all pairs $i,j$ of vertices in $S$, rerandomize the edge
$(i,j)$ where the probability of $(i,j)$ being in the graph is now $p$. Set
$G$ to be the resulting graph.

In Section 4, we compute the candidate moment matrix $\Lambda$ obtained by
using pseudo-calibration on this planted distribution.

######  Theorem 1.1.

Let $C_{p}>0$. There exists a constant $C>0$ such that for all sufficiently
small constants $\varepsilon>0$, if $k\leq n^{\frac{1}{2}-\varepsilon}$ and
$p=\frac{1}{2}+\frac{n^{-C_{p}\varepsilon}}{2}$, then with high probability,
the candidate moment matrix $\Lambda$ given by pseudo-calibraton for degree
$n^{C\varepsilon}$ Sum-of-Squares is PSD.

######  Corollary 1.2.

Let $C_{p}>0$. There exists a constant $C>0$ such that for all sufficiently
small constants $\varepsilon>0$, if $k\leq n^{\frac{1}{2}-\varepsilon}$ and
$p=\frac{1}{2}+\frac{n^{-C_{p}\varepsilon}}{2}$, then with high probability,
degree $n^{C\varepsilon}$ Sum-of-Squares cannot certify that a random graph
$G$ from $G(n,\frac{1}{2})$ does not have a subgraph of size $\approx k$ with
edge density $\approx p$.

##### Tensor PCA

Let $k\geq 2$ be an integer. We use the following distributions.

  * []

  * -

Random distribution: Sample $A$ from $\mathcal{N}(0,I_{[n]^{k}})$.

  * -

Planted distribution: Let $\lambda,\Delta>0$. Sample $u$ from
$\\{-\frac{1}{\sqrt{\Delta n}},0,\frac{1}{\sqrt{\Delta n}}\\}^{n}$ where the
values are taken with probabilites
$\frac{\Delta}{2},1-\Delta,\frac{\Delta}{2}$ respectively. Then sample $B$
from $\mathcal{N}(0,I_{[n]^{k}})$. Set $A=B+\lambda u^{\otimes k}$.

In Section 5, we compute the candidate moment matrix $\Lambda$ obtained by
using pseudo-calibration on this planted distribution.

######  Theorem 1.3.

Let $k\geq 2$ be an integer. There exist constants $C,C_{\Delta}>0$ such that
for all sufficiently small constants $\varepsilon>0$, if $\lambda\leq
n^{\frac{k}{4}-\varepsilon}$ and $\Delta=n^{-C_{\Delta}\varepsilon}$ then with
high probability, the candidate moment matrix $\Lambda$ given by pseudo-
calibration for degree $n^{C\varepsilon}$ Sum-of-Squares is PSD.

######  Corollary 1.4.

Let $k\geq 2$ be an integer. There exists a constant $C>0$ such that for all
sufficiently small constants $\varepsilon>0$, if $\lambda\leq
n^{\frac{k}{4}-\varepsilon}$, then with high probability, degree
$n^{C\varepsilon}$ Sum-of-Squares cannot certify that for a random tensor $A$
from $\mathcal{N}(0,I_{[n]^{k}})$, there is no vector $u$ such that
$\left\lVert u\right\rVert\approx 1$ and $\langle
A,\underbrace{x\otimes\ldots\otimes x}_{\text{k times}}\rangle\approx\lambda$.

##### Wishart model of Sparse PCA

We use the following distributions.

  * []

  * -

Random distribution: $v_{1},\ldots,v_{m}$ are sampled from
$\mathcal{N}(0,I_{d})$ and we take $S$ to be the $m\times d$ matrix with rows
$v_{1},\ldots,v_{m}$.

  * -

Planted distribution: Sample $u$ from
$\\{-\frac{1}{\sqrt{k}},0,\frac{1}{\sqrt{k}}\\}^{d}$ where the values are
taken with probabilites $\frac{k}{2d},1-\frac{k}{d},\frac{k}{2d}$
respectively. Then sample $v_{1},\ldots,v_{m}$ as follows. For each $i\in[m]$,
with probability $\Delta$, sample $v_{i}$ from $\mathcal{N}(0,I_{d}+\lambda
uu^{T})$ and with probability $1-\Delta$, sample $v_{i}$ from
$\mathcal{N}(0,I_{d})$. Finally, take $S$ to be the $m\times d$ matrix with
rows $v_{1},\ldots,v_{m}$.

In Section 6, we compute the candidate moment matrix $\Lambda$ obtained by
using pseudo-calibration on this planted distribution.

######  Theorem 1.5.

There exists a constant $C>0$ such that for all sufficiently small constants
$\varepsilon>0$, if
$m\leq\frac{d^{1-\varepsilon}}{\lambda^{2}},m\leq\frac{k^{2-\varepsilon}}{\lambda^{2}}$,
and there exists a constant $A$ such that $0<A<\frac{1}{4}$, $d^{4A}\leq k\leq
d^{1-A\varepsilon}$, and $\frac{\sqrt{\lambda}}{\sqrt{k}}\leq
d^{-A\varepsilon}$, then with high probability, the candidate moment matrix
$\Lambda$ given by pseudo-calibration for degree $d^{C\varepsilon}$ Sum-of-
Squares is PSD.

######  Corollary 1.6.

There exists a constant $C>0$ such that for all sufficiently small constants
$\varepsilon>0$, if
$m\leq\frac{d^{1-\varepsilon}}{\lambda^{2}},m\leq\frac{k^{2-\varepsilon}}{\lambda^{2}}$,
and there exists a constant $A$ such that $0<A<\frac{1}{4}$, $d^{4A}\leq k\leq
d^{1-A\varepsilon}$, and $\frac{\sqrt{\lambda}}{\sqrt{k}}\leq
d^{-A\varepsilon}$, then with high probability, the degree $d^{C\varepsilon}$
degree Sum-of-Squares cannot certify that for a random $m\times d$ matrix $S$
with Gaussian entries, there is no vector $u$ such that $u$ has $\approx k$
nonzero entries, $\left\lVert u\right\rVert\approx 1$, and $\left\lVert
Su\right\rVert^{2}\approx m+m{\Delta}\lambda$.

######  Remark 1.7.

Note that our planted distributions only approximately satisfy constraints
such as having a subgraph of size $k$, having a unit vector $u$, and having
$u$ be $k$-sparse. While we would like to use planted distributions which
satisfy such constraints exactly, these distributions don’t quite satisfy the
conditions of our machinery. This same issue appeared in the SoS lower bounds
for planted clique [BHK+16]. Resolving this issue is a subtle but important
open problem.

###  1.2 Relation to previous work on Planted Clique/Dense Subgraph, Tensor
PCA, and Sparse PCA

####  1.2.1 Planted Dense Subgraph

In the planted dense subgraph problem, we are given a random graph $G$ where a
dense subgraph of size $k$ has been planted and we are asked to find this
planted dense subgraph. This is a natural generalization of the $k$-clique
problem [Kar72] and has been subject to a long line of work over the years
(e.g. [FS+97, FPK01, Kho06, BCC+10, BCG+12, BKRW17, Man17]). In this work, we
consider the following certification variant of planted dense subgraph.

> Given a random graph $G$ sampled from the Erdős-Rényi model
> $G(n,\frac{1}{2})$, certify an upper bound on the edge density of the
> densest subgraph on $k$ vertices.

In [BHK+16], they show that for $k\leq n^{\frac{1}{2}-\varepsilon}$ for a
constant $\varepsilon>0$, the degree $o(\log n)$ Sum-of-Squares cannot
distinguish between a fully random graph sampled from $G(n,\frac{1}{2})$ from
a random graph which has a planted $k$-clique. This implies that degree
$o(\log n)$ SoS cannot certify an edge density better than $1$ for the densest
$k$-subgraph if $k\leq n^{\frac{1}{2}-\varepsilon}$.

In Corollary 1.2, we show that for $k\leq n^{\frac{1}{2}-\varepsilon}$ for a
constant $\varepsilon>0$, degree $n^{\Omega(\varepsilon)}$ SoS cannot certify
an edge density better than $\frac{1}{2}+\frac{1}{n^{O(\varepsilon)}}$. To the
best of our knowledge, this is the first result that proves such a lower bound
for SoS degrees as high as $n^{\Omega(\varepsilon)}$. When the SoS degree is
only $o(\log n)$, our result is not as strong as the work of [BHK+16].

We remark that when we take $k=n^{\frac{1}{2}-\varepsilon}$, the true edge
density of the densest $k$-subgraph is
$\frac{1}{2}+\frac{\sqrt{\log(n/k)}}{\sqrt{k}}+\operatorname{o}(\frac{1}{\sqrt{k}})\approx\frac{1}{2}+\frac{1}{n^{1/4-\varepsilon/2}}$
as was shown in [GZ19, Corollary 2] whereas, by Corollary 1.2, the SoS optimum
is as large as $\frac{1}{2}+\frac{1}{n^{\varepsilon}}$. This highlights a
significant additive difference in the optimum value.

####  1.2.2 Tensor PCA

The Tensor Principal Component Analysis problem, originally introduced by
[RM14], is a generalization of the PCA problem from machine learning to higher
order tensors. Given an order $k$ tensor of the form $\lambda u^{\otimes k}+B$
where $u\in\mathbb{R}^{n}$ is a unit vector and $B\in\mathbb{R}^{[n]^{k}}$ has
independent Gaussian entries, we would like to recover $u$. Here, $\lambda$ is
known as the signal-to-noise ratio.

This can be equivalently considered to be the problem of optimizing a
homogenous degree $k$ polynomial $f(x)$, with random Gaussian coefficients
over the unit sphere $\left\lVert x\right\rVert=1$. In general, polynomial
optimization over the unit sphere is a fundamental primitive with a lot of
connections to other areas of optimization (e.g. [FK08, BV09, BH17, BKS14,
BKS15, BGG+17]). Tensor PCA is an average case version of the above problem
and has been studied before in the literature [RM14, HSS15, BGL16, HKP+17]. In
this work, we consider the certification version of this average case problem.

> For an integer $k\geq 2$, given a random tensor $A\in\mathbb{R}^{[n]^{k}}$
> with entries sampled independently from $\mathcal{N}(0,1)$, certify an upper
> bound on $\langle A,x^{\otimes k}\rangle$ over unit vectors $x$.

In [BGL16], it was shown that $q\leq n$ levels of SoS certifies an upper bound
of $\frac{2^{O(k)}(n\cdot\text{polylog}(n))^{k/4}}{q^{k/4-1/2}}$ for the
Tensor PCA problem. When $q=n^{\varepsilon}$ for sufficiently small
$\varepsilon$, this gives an upper bound of $n^{\frac{k}{4}-O(\varepsilon)}$.
Corollary 1.4 shows that this is tight.

In [HKP+17], they state a theorem similar to Corollary 1.4 and observe that it
can be proved by applying the techniques used to prove the SoS lower bounds
for planted clique. However, they do not give an explicit proof. Also, while
they consider the setting where the random distribution has entries from
$\\{-1,1\\}$, we work with $\mathcal{N}(0,1)$. We remark that our machinery
can recover their result.

When $k=2$, the maximum value of $\langle x^{\otimes k},A\rangle$ over the
unit sphere $\left\lVert x\right\rVert^{2}=1$ is precisely the largest
eigenvalue of $(A+A^{T})/2$ which is $\Theta(\sqrt{n})$ with high probability.
For any integer $k\geq 2$, the true maximum of $\langle x^{\otimes
k},A\rangle$ over $\left\lVert x\right\rVert^{2}=1$ is $O(\sqrt{n})$ with high
probability [TS14]. In contrast, by Corollary 1.4, the optimum value of the
degree $n^{\varepsilon}$ SoS is as large as $n^{\frac{k}{4}-O(\varepsilon)}$.
This exhibits an integrality gap of
$n^{\frac{k}{4}-\frac{1}{2}-O(\varepsilon)}$.

####  1.2.3 Wishart model of Sparse PCA

The Wishart model of Sparse PCA, also known as the Spiked Covariance model,
was originally proposed by [JL09]. In this problem, we observe $m$ vectors
$v_{1},\ldots,v_{m}\in\mathbb{R}^{d}$ from the distribution
$\mathcal{N}(0,I_{d}+\lambda uu^{T})$ where $u$ is a $k$-sparse unit vector,
and we would like to recover $u$. Here, the sparsity of a vector is the number
of nonzero entries and $\lambda$ is known as the signal-to-noise ratio.

Sparse PCA is a fundamental problem that has applications in a diverse range
of fields (e.g. [WLY12, NYS11, Maj09, TPW14, CK09, AMS11]). It’s known that
vanilla PCA does not yield good estimators in high dimensional settings
[BAP+05, Pau07, JL09]. A large volume of work has gone into studying Sparse
PCA and it’s variants, both from an algorithmic perspective (e.g. [AW08, Ma13,
KNV+15, DM16, WBS+16]) as well as from an inapproximability perspective (e.g.
[BR13a, MW15, DKS17, HKP+17, BB19]).

Between this work and prior works, we completely understand the parameter
regimes where sparse PCA is easy or conjectured to be hard up to
polylogarithmic factors.

  * -

If $m\gg\frac{k^{2}}{\lambda^{2}}$ then the sparse vector can be recovered by
diagonal thresholding[JL09, AW08], covariance thresholding [KNV+15, DM16], or
SoS [dKNS20].

  * -

If $m\geq d$ and $m\gg\frac{d}{\lambda^{2}}$ or $m\leq d$ and
$m\gg\frac{d}{\lambda}$ then vanilla PCA can recover the sparse vector (i.e.
we do not need to use the fact that the vector is sparse) (e.g. [BR+13b,
dKNS20]).

  * -

If $m\leq d$, $\frac{d}{\lambda^{2}}\ll m\ll\frac{d}{\lambda}$, and
$m\gg\frac{k}{\lambda}$ then there is an efficient spectral algorithm to
recover the sparse vector (e.g. [dKNS20]).

  * -

If $m\leq d$, $\frac{d}{\lambda^{2}}\ll m\ll\frac{d}{\lambda}$, and
$m\ll\frac{k}{\lambda}$ then there is a simple spectral algorithm which
distinguishes the planted distribution from the random distribution but it is
information theoretically impossible to recover the sparse vector [dKNS20,
Appendix E].

  * -

If $m\ll\frac{k^{2}}{\lambda^{2}}$ and $m\ll\frac{d}{\lambda^{2}}$ then it is
conjectured to be hard to distinguish between the random and the planted
distributions. We discuss the evidence for this below.

For the parameter regime where $m\ll\frac{k^{2}}{\lambda^{2}}$ and
$m\ll\frac{d}{\lambda^{2}}$, several SoS lower bounds have been shown. The
works [KNV+15, BR+13b] obtain degree 2 SoS lower bounds. [MW15] obtain degree
4 SoS lower bounds using different techniques. The bounds they obtain are
tight up to polylogarithmic factors when $\lambda$ is a constant. The work
[HKP+17] considers the related Wigner model of Sparse PCA and they state
degree $d^{\varepsilon}$ SoS lower bounds, without explicitly proving these
bounds. They ask for similar SoS lower bounds in the Wishart model. We almost
fully resolve their questions in this work with Corollary 1.6. Our machinery
can also recover their results on the Wigner model.

In [dKNS20], they prove that if $m\leq\frac{d}{\lambda^{2}}$ and
$m\leq\left(\frac{k^{2}}{\lambda^{2}}\right)^{1-\Omega(\varepsilon)}$, then
degree $n^{\varepsilon}$ polynomials cannot distinguish the random and planted
distributions. Corollary 1.6 says that under slightly stronger assumptions,
degree $n^{\varepsilon}$ Sum-of-Squares cannot distinguish the random and
planted distributions, so we confirm that SoS is no more powerful than low
degree polynomials in this setting.

###  1.3 Comparison to Other Sum-of-Squares Lower Bounds on Certification
Problems

In a seminal work, [BHK+16] proved sum of squares lower bounds for the planted
clique problem. Our machinery greatly generalizes the techniques of this
paper. That said, for a technical reason, our machinery actually doesn’t quite
handle planted clique (See Remark 3.35).

Similar to this paper, [HKP+17] also observed that the techniques used in
[BHK+16] can be used to give Sum-of-Squares lower bounds for $\pm{1}$ variants
of tensor PCA and sparse PCA, though this is not made explicit. In this paper,
we use our machinery to make these lower bounds explicit. We also handle the
Wishart model of sparse PCA, which is significantly harder to prove lower
bounds for.

[KMOW17] proved that for random constraint satisfaction problems (CSPs) where
the predicate has a balanced pairwise independent distribution of solutions,
with high probability, degree $\Omega(n)$ SoS is required to certify that
these CSPs do not have a solution. While the pseudo-expectation values used by
[KMOW17] can also be derived using pseudo-calibration, the analysis for
showing that the moment matrix is PSD is very different. It is an interesting
question whether or not it is possible to unify these analyses.

[MRX20] showed that it’s possible to lift degree $2$ SoS solutions to degree
$4$ SoS solutions under suitable conditions, and used it to obtain degree $4$
SoS lower bounds for average case $d$-regular Max-Cut and the Sherrington
Kirkpatrick problem. Their construction is inspired by pseudo-calibration and
their analysis also goes via graph matrices.

Recently, [GJJ+20] proved degree $n^{\varepsilon}$ SoS lower bounds for the
Sherrington-Kirkpatrick problem via an intermediate problem known as Planted
Affine Planes. Their construction and analysis also goes via pseudo-
calibration and graph matrices, but since the constructed moment matrix had a
nontrivial nullspace, they had to use different techniques to handle them.
However, once this nullspace is taken into account, the moment matrix is
dominated by its expected value, so using our machinery would be overkill.

[Kun20] recently proposed a technique to lift degree $2$ SoS lower bounds to
higher levels and applied it to construct degree $6$ lower bounds for the
Sherrington-Kirkpatrick problem. Interestingly, their construction does not go
via pseudo-calibration.

###  1.4 Related Algorithmic Techniques

##### Low degree polynomials

Consider a problem where the input is sampled from one of two distributions
and we would like to identify which distribution it was sampled from. Usually,
one distribution is the random distribution while the other is a planted
distribution that contains a given structure not present in the random
distribution. In this setting, a closely related method is to use low degree
polynomials to try and distinguish the two distributions. More precisely, if
there is a low degree polynomial such that its expected value on the random
distribution is very different than its expected value on the planted
distribution, this distinguishes the two distributions. Recently, this method
has been shown to be an excellent heuristic, as it recovers the conjectured
hardness thresholds for several problems and is considerably easier to analyze
[HKP+17, Hop18, KWB19].

That said, it is an open question whether low degree polynomials generally
have the same power as the SoS hierarchy or if there are situations where the
SoS hierarchy is more powerful. In this paper, we confirm that for tensor PCA
and the Wishart model of sparse PCA with slightly adjusted planted
distributions, the SoS hierarchy is no more powerful than low-degree
polynomials.

##### The Statistical Query Model

The statistical query model is another popular restricted class of algorithms
introduced by [Kea98]. In this model, for an underlying distribution, we can
access it by querying expected value of functions of the distribution.
Concretely, for a distribution $D$ on $\mathbb{R}^{n}$, we have access to it
via an oracle that given as query a function
$f:\mathbb{R}^{n}\rightarrow[-1,1]$ returns $\mathop{\mathbb{E}}_{x\sim
D}f(x)$ upto some additive adversarial error. SQ algorithms capture a broad
class of algorithms in statistics and machine learning and has also been used
to study information-computation tradeoffs. There has also been significant
work trying to understand the limits of SQ algorithms (e.g. [FGR+17, FPV18,
DKS17]). The recent work [BBH+20] showed that low degree polynomials and
statistical query algorithms have equivalent power under mild conditions. It’s
an interesting open question whether or not SQ algorithms have the same power
as Sum-of-Squares algorithms.

###  1.5 Organization of the paper

The remainder of this paper is organized as follows. In Section 2, we give
some preliminaries. In particular, we describe the Sum-of-Squares hierarchy
and present a brief overview of the machinery and some proof techniques that
we use. In Section 3, we present the informal statement of the main theorem.
In Section 4, Section 5 and Section 6, we qualitatively verify the conditions
of the machinery for planted slightly denser subgraph, tensor PCA, and sparse
PCA respectively. While these sections only verify the qualitative conditions,
the results in these sections are precise and will be reused in Section 11,
Section 12 and Section 13 to fully verify the conditions of the machinery. In
Section 7, we introduce all the formal definitions and state the main theorem
in full generality. In Section 8, we prove the main theorem while abstracting
out the choice of several functions. In Section 9, we choose these functions
so that that they satisfy the conditions needed for our main theorem. In
Section 10, we give tools for verifying a technical condition of our machinery
which is related to truncation error. Finally, in Section 11, Section 12 and
Section 13, we verify all the conditions necessary to prove Theorem 1.1,
Theorem 1.3 and Theorem 1.5 respectively.

##  2 Preliminaries and proof overview

###  2.1 The Sum of Squares Hierarchy

We will first introduce the notion of a pseudoexpectation operator for a set
of polynomial constraints and then describe the Sum-of-Squares relaxation for
a polynomial optimization problem.

For an integer $d$, Let $\mathbb{R}^{\leq d}[x_{1},\ldots,x_{n}]$ be the set
of polynomials on $x_{1}\ldots,x_{n}$ of degree at most $d$. We denote the
degree of a polynomial $f\in\mathbb{R}[x_{1},\dots,x_{n}]$ by $\deg(f)$.

######  Definition 2.1 (Pseudoexpectation operator).

Given polynomial constraints $g_{1}(x)=0,\ldots,g_{m}(x)=0$ on variables
$x_{1},\dots,x_{n}$ such that $deg(g_{i})\leq D$ for an integer $D\geq 0$. For
an even integer $d\geq D$, a degree-$d$ pseudoexpectation operator
$\tilde{\mathop{\mathbb{E}}}$ satisfying these constraints is an operator
$\tilde{\mathop{\mathbb{E}}}\colon\mathbb{R}^{\leq
d}[x_{1},\dots,x_{n}]\rightarrow\mathbb{R}$ satisfying:

  1. 1.

$\tilde{\mathop{\mathbb{E}}}[1]=1$,

  2. 2.

$\tilde{\mathop{\mathbb{E}}}$ is an $\mathbb{R}$-linear operator, i.e.,
$\tilde{\mathop{\mathbb{E}}}[f+cg]=\tilde{\mathop{\mathbb{E}}}[f]+c\tilde{\mathop{\mathbb{E}}}[g]$
for every $f,g\in\mathbb{R}^{\leq d}[x_{1},\dots,x_{n}],c\in\mathbb{R}$,

  3. 3.

$\tilde{\mathop{\mathbb{E}}}[g_{i}\cdot f]=0$ for every $i=1,\ldots,m$ and
$f\in\mathbb{R}^{\leq d}[x_{1},\dots,x_{n}]$ with $\deg(f\cdot g_{i})\leq d$.

  4. 4.

$\tilde{\mathop{\mathbb{E}}}[f^{2}]\geq 0$ for every $f\in\mathbb{R}^{\leq
d}[x_{1},\dots,x_{n}]$ with $\deg(f^{2})\leq d$.

The notion of $\tilde{\mathop{\mathbb{E}}}$ generalizes the standard
expectation operator. The idea is that optimizing over this larger space of
pseudoexpectation operators can be formulated as a semidefinite programming
problem and hence, will serve as a relaxation of our program that can be
solved efficiently.

Formally, consider an optimization task on $n$ variables
$x_{1},\ldots,x_{n}\in\mathbb{R}$ formulated as maximizing a polynomial $f(x)$
subject to polynomial constraints $g_{1}(x)=0,\ldots,g_{m}(x)=0$. Suppose all
the polynomials $f,g_{1},\ldots,g_{m}$ have degree at most $D$. Then, for an
even integer $d\geq D$, the degree $d$ Sum-of-Squares relaxation of this
program is as follows: Over all pseudoexpectation operators
$\tilde{\mathop{\mathbb{E}}}$ satisfying
$\tilde{\mathop{\mathbb{E}}}[g_{1}(x)]=0,\ldots,\tilde{\mathop{\mathbb{E}}}[g_{m}(x)]=0$,
output the maximum value of $\tilde{\mathop{\mathbb{E}}}[f(x)]$.

To prove an SoS lower bound, we need to exhibit an operator
$\tilde{\mathop{\mathbb{E}}}$ that satisfies these constraints with optimum
value of $\tilde{\mathop{\mathbb{E}}}[f(x)]$ being far away from the true
optimum.

In most cases, when constructing $\tilde{\mathop{\mathbb{E}}}$, the condition
Item 4 in Definition 2.1 is the most technically challenging condition to
satisfy. It can be equivalently stated as a positive semidefiniteness
condition of an associated matrix called the moment matrix.

To define the moment matrix, we need to set up some more notation.

For an integer $d\geq 0$, let ${\mathcal{I}}_{d}$ denote the set of all tuples
$(t_{1},\ldots,t_{n})$ such that $t_{i}\geq 0$ for all $i$ and $\sum t_{i}\leq
d$. For $I=(t_{1},\ldots,t_{n})\in{\mathcal{I}}_{d}$, denote by
$x^{I}:=x_{1}^{t_{1}}x_{2}^{t_{2}}\ldots x_{n}^{t_{n}}$.

######  Definition 2.2 (Moment Matrix of $\tilde{\mathop{\mathbb{E}}}$).

For a degree $2d$ pseudoexpectation operator $\tilde{\mathop{\mathbb{E}}}$ on
variables $x_{1},\ldots,x_{n}$, define the associated moment matrix $\Lambda$
to be a matrix with rows and columns indexed by ${\mathcal{I}}_{d}$ such that
the entry corresponding to row $I$ and column $J$ is

$\Lambda[I,J]:=\tilde{\mathop{\mathbb{E}}}\left[x^{I}\cdot x^{J}\right].$

It is easy to verify that Item 4 in Definition 2.1 equivalent to
$\Lambda\succeq 0$.

The machinery in this paper provides general conditions under which we can
show that with high probability, $\Lambda\succeq 0$.

###  2.2 Pseudo-calibration

Pseudo-calibration is a heuristic developed in [BHK+16] to construct a
candidate pseudoexpectation operator $\tilde{\mathop{\mathbb{E}}}$ and a
corresponding moment matrix $\Lambda$ for random vs planted problems. This
will be the starting point for all our applications. Here, we will describe
the heuristic and show an example of how to use it.

Let $\nu$ denote the random distribution and $\mu$ denote the planted
distribution. Let $v$ denote the input and $x$ denote the variables for our
SoS relaxation. The idea is that, for an input $v$ sampled from $\nu$ and any
polynomial $f(x)$ of degree at most the SoS degree, pseudo-calibration
proposes that for any low-degree test $g(v)$, the correlation of
$\tilde{\mathop{\mathbb{E}}}[f]$ should match in the planted and random
distributions. That is,

$\mathop{\mathbb{E}}_{v\sim\nu}[\tilde{\mathop{\mathbb{E}}}[f(x)]g(v)]=\mathop{\mathbb{E}}_{(x,v)\sim\mu}[f(x)g(v)]$

Let ${\mathcal{F}}$ denote the Fourier basis of polynomials for the input $v$.
By choosing different basis functions from ${\mathcal{F}}$ as choices for $g$
such that the degree is at most $n^{\varepsilon}$ (hence the term low-degree
test), we get all lower order Fourier coefficients for
$\tilde{\mathop{\mathbb{E}}}[f(x)]$ when considered as a function of $v$.
Furthermore, the higher order coefficients are set to be $0$ so that the
candidate pseudoexpectation operator can be written as

$\tilde{\mathop{\mathbb{E}}}f(x)=\sum_{\begin{subarray}{c}g\in{\mathcal{F}}\\\
deg(g)\leq
n^{\varepsilon}\end{subarray}}\mathop{\mathbb{E}}_{v\sim\nu}[\tilde{\mathop{\mathbb{E}}}[f(x)]g(v)]g(v)=\sum_{\begin{subarray}{c}g\in{\mathcal{F}}\\\
deg(g)\leq
n^{\varepsilon}\end{subarray}}\mathop{\mathbb{E}}_{(x,v)\sim\mu}[[f(x)]g(v)]g(v)$

The coefficients $\mathop{\mathbb{E}}_{(x,v)\sim\mu}[[f(x)]g(v)]$ can be
explicitly computed in many settings, which therefore gives an explicit
pseudoexpectation operator $\tilde{\mathop{\mathbb{E}}}$.

An advantage of pseudo-calibration is that this construction automatically
satisfies some nice properties that the pseudoexpectation
$\tilde{\mathop{\mathbb{E}}}$ should satisfy. It’s linear in $v$ by
construction. For all polynomial equalities of the form $f(x)=0$ that is
satisfied in the planted distribution, it’s true that
$\tilde{\mathop{\mathbb{E}}}[f(x)]=0$. For other polynomial equalities of the
form $f(x,v)=0$ that are satisfied in the planted distribution, the equality
$\tilde{\mathop{\mathbb{E}}}[f(x,v)]=0$ is approximately satisfied. In most
cases, $\tilde{\mathop{\mathbb{E}}}$ can be mildly adjusted to satisfy these
exactly.

The condition $\tilde{\mathop{\mathbb{E}}}[1]=1$ is not automatically
satisfied but in most applications, we usually require that
$\tilde{\mathop{\mathbb{E}}}[1]=1\pm\operatorname{o}(1)$. Indeed, this has
been the case for all known successful applications of pseudo-calibration.
Once we have this, we simply set our final pseudoexpectation operator to be
$\tilde{\mathop{\mathbb{E}}}^{\prime}$ defined as
$\tilde{\mathop{\mathbb{E}}}^{\prime}[f(x)]=\tilde{\mathop{\mathbb{E}}}[f(x)]/\tilde{\mathop{\mathbb{E}}}[1]$.

We remark that the condition
$\tilde{\mathop{\mathbb{E}}}[1]=1\pm\operatorname{o}(1)$ has been quite
successful in predicting the right thresholds between approximability and
inapproximability[HKP+17, Hop18, KWB19].

##### Example: Planted Clique

As an warmup, we review the pseudo-calibration calculation for planted clique.
Here, the random distribution $\nu$ is $G(n,\frac{1}{2})$.

The planted distribution $\mu$ is as follows. For a given integer $k$, first
sample $G^{\prime}$ from $G(n,\frac{1}{2})$, then choose a random subset $S$
of the vertices where each vertex is picked independently with probability
$\frac{k}{n}$. For all pairs $i,j$ of distinct vertices in $S$, add the edge
$(i,j)$ to the graph if not already present. Set $G$ to be the resulting
graph.

The input is given by $G\in\\{-1,1\\}^{\binom{[n]}{2}}$ where $G_{i,j}$ is $1$
if the edge $(i,j)$ is present and $-1$ otherwise. Let $x_{1},\ldots,x_{n}$ be
the boolean variables for our SoS program such that $x_{i}$ indicates if $i$
is in the clique.

######  Definition 2.3.

Given a set of vertices $V\subseteq[n]$, define $x_{V}=\prod_{v\in V}{x_{v}}$.

######  Definition 2.4.

Given a set of possible edges $E\subseteq\binom{[n]}{2}$, define
$\chi_{E}=(-1)^{|E\setminus E(G)|}=\prod_{(i,j)\in E}G_{i,j}$.

Pseudo-calibration says that for all small $V$ and $E$,

$\mathop{\mathbb{E}}_{G\sim\nu}\left[\tilde{E}[x_{V}]\chi_{E}\right]=\mathop{\mathbb{E}}_{\mu}\left[x_{V}{\chi_{E}}\right]$

Using standard Fourier analysis, this implies that if we take

$c_{E}=\mathop{\mathbb{E}}_{\mu}\left[x_{V}{\chi_{E}}\right]=\left(\frac{k}{n}\right)^{|V\cup
V(E)|}$

where $V(E)$ is the set of the endpoints of the edges in $E$, then for all
small $V$,

$\tilde{\mathop{\mathbb{E}}}[x_{V}]=\sum_{E:E\text{ is
small}}{{c_{E}}\chi_{E}}=\sum_{E:E\text{ is
small}}{\left(\frac{k}{n}\right)^{|V\cup V(E)|}\chi_{E}}$

Since the values of $\tilde{\mathop{\mathbb{E}}}[x_{V}]$ are known, by multi-
linearity, this can be naturally extended to obtain values
$\tilde{\mathop{\mathbb{E}}}[f(x)]$ for any polynomial $f$ of degree at most
the SoS degree.

###  2.3 Proof overview and techniques

In this section, we describe some ideas behind our machinery.

As explained above, pseudo-calibration will give us a candidate
pseudoexpectation operator $\tilde{\mathop{\mathbb{E}}}$ and we can consider a
corresponding moment matrix $\Lambda$. For example, in the case of planted
clique, $\Lambda$ has rows and columns indexed by sub-tuples of $[n]$ of size
at most $d$, such that

$\Lambda[I,J]=\sum_{E:E\text{ is small}}\left(\frac{k}{n}\right)^{|I\cup J\cup
V(E)|}\chi_{E}$

for all sub-tuples $I,J$ of $[n]$ of size at most $d$. We would like to prove
that $\Lambda\succeq 0$ with high probability.

The machinery gives a set of conditions under which we can show that
$\Lambda\succeq 0$ with high probability. Our first step will be decompose
$\Lambda$ into a linear combination of graph matrices.

##### Graph matrices

Graph matrices were originally introduced by [BHK+16, MP16] and later
generalized in [AMP20]. We use the generalized graph matrices in our analysis.

Each graph matrix is a matrix valued function of the input, that can be
identified by a graph with labeled edges that we call a shape. Informally,
graph matrices will form a basis for all matrix valued functions of the input
that have a certain symmetry. In particular, $\Lambda$ is one such matrix
valued function and can thus be decomposed into graph matrices. For a shape
$\alpha$, the graph matrix associated to $\alpha$ is denoted by $M_{\alpha}$.

Graph matrices have several useful properties. Firstly, $\left\lVert
M_{\alpha}\right\rVert$ can be bounded with high probability in terms of
simple combinatorial properties of the shape $\alpha$. Secondly, when we
multiply two graph matrices $M_{\alpha},M_{\beta}$ corresponding to shapes
$\alpha,\beta$, it approximately equals the graph matrix
$M_{\alpha\circ\beta}$ where the shape $\alpha\circ\beta$, called the
composition of the two shapes $\alpha\circ\beta$, is easy to describe
combinatorially.

These makes graph matrices a convenient tool to analyze the moment matrix. In
our setting, the moment matrix decomposes as
$\Lambda=\sum\lambda_{\alpha}M_{\alpha}$ where the sum is over all shapes
$\alpha$ and $\lambda_{\alpha}\in\mathbb{R}$ are the coefficients that arise
from pseudo-calibration.

##### Decomposing Shapes

For graph matrices $\alpha,\beta$, $M_{\alpha}M_{\beta}\approx
M_{\alpha\circ\beta}$ where we define the composition of two shapes
$\alpha\circ\beta$ to be a larger shape that is obtained by concatenating the
shapes $\alpha,\beta$. This equality is only approximate and handling it
precisely is a significant source of difficulty in our analysis. Shape
composition is also associative, hence we can define composition of three
shapes.

A crucial idea for our machinery is that for any shape $\alpha$, there exists
a canonical and unique decomposition of $\alpha$ as
$\sigma\circ\tau\circ\sigma^{\prime T}$ satisfying some nice structural
properties, for shapes $\sigma,\tau$ and $\sigma^{\prime T}$. Here,
$\sigma,\tau,\sigma^{\prime T}$ are called the left part, the middle part and
the right part of $\alpha$ respectively. Using this, our moment matrix can be
written as

$\Lambda=\sum_{\alpha}\lambda_{\alpha}M_{\alpha}=\sum_{\sigma,\tau,\sigma^{\prime}}\lambda_{\sigma\circ\tau\circ\sigma^{\prime
T}}M_{\sigma\circ\tau\circ\sigma^{\prime T}}$

##### Giving a PSD factorization

We first consider the terms
$\sum_{\sigma,\sigma^{\prime}}\lambda_{\sigma\circ\sigma^{\prime
T}}M_{\sigma\circ\sigma^{\prime
T}}\approx\sum_{\sigma,\sigma^{\prime}}\lambda_{\sigma\circ\sigma^{\prime
T}}M_{\sigma}M_{\sigma^{\prime T}}$ where $\tau$ corresponds to an identity
matrix and can be ignored.

If there existed real numbers $v_{\sigma}$ for all left shapes $\sigma$ such
that $\lambda_{\sigma\circ\sigma^{\prime T}}=v_{\sigma}v_{\sigma^{\prime}}$,
then we would have

$\sum_{\sigma,\sigma^{\prime}}\lambda_{\sigma\circ\sigma^{\prime
T}}M_{\sigma}M_{\sigma^{\prime
T}}=\sum_{\sigma,\sigma^{\prime}}v_{\sigma}v_{\sigma^{\prime}}M_{\sigma}M_{\sigma^{\prime
T}}=(\sum_{\sigma}v_{\sigma}M_{\sigma})(\sum_{\sigma}v_{\sigma}M_{\sigma})^{T}\succeq
0$

which shows that the contribution from these terms is positive semidefinite.
Note that the existence of $v_{\sigma}$ can be relaxed as follows. Let $H$ be
the matrix with rows and columns indexed by left shapes $\sigma$ such that
$H(\sigma,\sigma^{\prime})=\lambda_{\sigma\circ\sigma^{\prime T}}$. If $H$ is
positive semidefinite then the contribution from these terms will also be
positive semidefinite. In fact, this will be the first condition of our main
theorem, Theorem 7.101.

##### Handling terms with a non-trivial middle part

Unfortunately, we also have terms $\lambda_{\sigma\circ\tau\circ\sigma^{\prime
T}}M_{\sigma\circ\tau\circ\sigma^{\prime T}}$ where $\tau$ is non-trivial. Our
strategy will be to charge these terms to other terms.

A starting point for our argument is the following inequality. For left shape
$\sigma$, middle shape $\tau$ and right shape $\sigma^{\prime T}$, and real
numbers $a,b$,

$(aM_{\sigma}-bM_{\sigma^{\prime}}M_{\tau^{T}})(aM_{\sigma}-bM_{\sigma^{\prime}}M_{\tau^{T}})^{T}\succeq
0$

which rearranges to

$\displaystyle ab(M_{\sigma}M_{\tau}M_{\sigma^{\prime
T}}+(M_{\sigma}M_{\tau}M_{\sigma^{\prime T}})^{T})$ $\displaystyle\preceq
a^{2}M_{\sigma}M_{\sigma^{T}}+b^{2}M_{\sigma^{\prime}}M_{\tau^{T}}M_{\tau}M_{\sigma^{\prime
T}}$ $\displaystyle\preceq a^{2}M_{\sigma}M_{\sigma^{T}}+b^{2}\left\lVert
M_{\tau}\right\rVert^{2}M_{\sigma^{\prime}}M_{\sigma^{\prime T}}$

If it is true that $\lambda_{\sigma\circ\tau\circ\sigma^{\prime
T}}^{2}\left\lVert
M_{\tau}\right\rVert^{2}\leq\lambda_{\sigma\circ\sigma^{T}}\lambda_{\sigma^{\prime}\circ\sigma^{\prime
T}}$, then we can choose $a,b$ such that
$a^{2}\leq\lambda_{\sigma\circ\sigma^{T}},b^{2}\left\lVert
M_{\tau}\right\rVert^{2}\leq\lambda_{\sigma^{\prime}\circ\sigma^{\prime T}}$
and $ab=\lambda_{\sigma\circ\tau\circ\sigma^{\prime T}}$. This will
approximately imply

$\lambda_{\sigma\circ\tau\circ\sigma^{\prime
T}}(M_{\sigma\circ\tau\circ\sigma^{\prime
T}}+M_{\sigma\circ\tau\circ\sigma^{\prime
T}}^{T})\preceq\lambda_{\sigma\circ\sigma^{T}}M_{\sigma\circ\sigma^{T}}+\lambda_{\sigma^{\prime}\circ\sigma^{\prime
T}}M_{\sigma^{\prime}\circ\sigma^{\prime T}}$

which will give us a way to charge terms with a nontrivial middle part against
terms with a trivial middle part.

While we could try to apply this inequality term by term, it is not strong
enough to give us our results. Instead, we generalize this inequality. This
will lead us to the second condition of our main theorem, Theorem 7.101.

##### Handing intersection terms

There’s one important technicality in the above heuristic calculations.
Whenever we multiply two graph matrices $M_{\alpha},M_{\beta}$, it is only
approximately equal to $M_{\alpha\circ\beta}$. All the other error terms have
to be carefully handled in our analysis. We call these terms intersection
terms.

These intersection terms themselves turn out to be graph matrices and our
strategy is to now recursively decompose them into
$\sigma_{2}\circ\tau_{2}\circ\sigma_{2}^{\prime T}$ and apply the previous
ideas. A similar approach was undertaken in [BHK+16] but this work generalizes
it significantly. To do this methodically, we employ several ideas such as the
notion of intersection patterns and the generalized intersection tradeoff
lemma (see Section 8). Properly handling the intersection terms is one of the
most technically intensive parts of our work.

This analysis leads us to condition 3 of Theorem 7.101.

##### Applying the machinery

To apply the machinery to our problems of interest, we verify the spectral
conditions that our coefficients should satisfy so that we can use Theorem
7.101. The Planted slightly denser subgraph application is straightforward and
will serve as a good warmup to understand our machinery. In the applications
to Tensor PCA and Sparse PCA, the shapes corresponding to the graph matrices
with nonzero coefficients have nice structural properties that will be crucial
for our analysis. We exploit this structure and use novel charging arguments
to verify the conditions of our machinery.

##  3 Informal Description of our Machinery

In this section, we informally describe our machinery for proving sum of
squares lower bounds on planted problems. Our goal for this section is to
qualitatively state the conditions under which we can show that the moment
matrix $\Lambda$ is PSD with high probability (see Theorem 3.32). For
simplicity, in this section we restrict ourselves to the setting where the
input is $\\{-1,1\\}^{\binom{n}{2}}$ (i.e. a random graph on $n$ vertices). We
also defer the proofs of several important facts until Section 7. In Section
7, we give the general definitions, fill in the missing proofs, and give the
full, quantitative statement of our main result (see Theorem 7.101).

###  3.1 Fourier analysis for matrix-valued functions: ribbons, shapes, and
graph matrices

For our machinery, we need the definitions of ribbons, shapes, and graph
matrices from [AMP20].

####  3.1.1 Ribbons

_Ribbons_ lift the usual Fourier basis for functions $\\{f\,:\,\\{\pm
1\\}^{n\choose 2}\rightarrow{\mathbb{R}}\\}$ to matrix-valued functions.

######  Definition 3.1 (Simplified ribbons – see Definition 7.22).

Let $n\in{\mathbb{N}}$. A ribbon $R$ is a tuple $(E_{R},A_{R},B_{R})$ where
$E_{R}\subseteq{n\choose 2}$ and $A_{R},B_{R}$ are tuples of elements in
$[n]$. $R$ thus specifies:

  1. 1.

A Fourier character $\chi_{E_{R}}$.

  2. 2.

Row and column indices $A_{R}$ and $B_{R}$.

We think of $R$ as a graph with vertices

$V(R)=\\{\text{ endpoints of $(i,j)\in E_{R}$ }\\}\cup A_{R}\cup B_{R}$

and edges $E(R)=E_{R}$, where $A_{R},B_{R}$ are distinguished tuples of
vertices.

######  Definition 3.2 (Matrix-valued function for a ribbon $R$).

Given a ribbon $R$, we define the matrix valued function $M_{R}\,:\,\\{\pm
1\\}^{n\choose
2}\rightarrow{\mathbb{R}}^{\frac{n!}{(n-|A_{R}|)!}\times\frac{n!}{(n-|B_{R}|)!}}$
to have entries $M(A_{R},B_{R})=\chi_{E_{R}}$ and $M(A^{\prime},B^{\prime})=0$
whenever $A^{\prime}\neq A_{R}$ or $B^{\prime}\neq B_{R}$.

The following proposition captures the main property of the matrix-valued
functions $M_{R}$ – they are an orthonormal basis. We leave the proof to the
reader.

######  Proposition 3.3.

The matrix-valued functions $M_{R}$ form an orthonormal basis for the vector
space of matrix valued functions with respect to the inner product

$\langle M,M^{\prime}\rangle=\mathop{\mathbb{E}}_{G\sim\\{\pm 1\\}^{n\choose
2}}\left[\operatorname{Tr}\left(M(G)(M^{\prime}(G))^{\top}\right)\right].$

####  3.1.2 Shapes and Graph Matrices

As described above, _ribbons_ are an orthonormal basis for matrix-valued
functions. However, we will need an orthogonal basis for the subset of those
functions which are symmetric with respect to the action of $S_{n}$. For this,
we use _graph matrices_ , which are described by _shapes_. The idea is that
each ribbon $R$ has a shape $\alpha$ which is obtained by replacing the
vertices of $R$ with unspecified indices. Up to scaling, the graph matrix
$M_{\alpha}$ is the average of $M_{\pi(R)}$ over all permutations $\pi\in
S_{n}$.

######  Definition 3.4 (Simplified shapes – see Definition 7.34).

Informally, a shape $\alpha$ is just a ribbon $R$ where the vertices are
specified by variables rather than having specific values in $[n]$. More
precisely, a shape $\alpha=(V(\alpha),E(\alpha),U_{\alpha},V_{\alpha})$ is a
graph on vertices $V(\alpha)$, with

  1. 1.

Edges $E(\alpha)\subseteq{{V(\alpha)}\choose 2}$

  2. 2.

Distinguished tuples of vertices $U_{\alpha}=(u_{1},u_{2},\dots)$ and
$V_{\alpha}=(v_{1},v_{2},\dots)$, where $u_{i},v_{i}\in V(\alpha)$.

(Note that $V(\alpha)$ and $V_{\alpha}$ are not the same object!)

######  Definition 3.5 (Shape transposes).

Given a shape $\alpha$, we define $\alpha^{\top}$ to be the shape $\alpha$
with $U_{\alpha}$ and $V_{\alpha}$ swapped i.e. $U_{\sigma^{\top}}=V_{\sigma}$
and $V_{\sigma^{\top}}=U_{\sigma}$. Note that
$M_{\alpha^{\top}}=M_{\alpha}^{\top}$, where $M_{\alpha}^{\top}$ is the usual
transpose of the matrix-valued function $M_{\alpha}$.

######  Definition 3.6 (Graph matrices).

Let $\alpha$ be a shape. The graph matrix $M_{\alpha}\,:\,\\{\pm
1\\}^{n\choose
2}\rightarrow{\mathbb{R}}^{\frac{n!}{(n-|U_{\alpha}|)!}\times\frac{n!}{(n-|V_{\alpha}|)!}}$
is defined to be the matrix-valued function with $A,B$-th entry

$M_{\alpha}(A,B)=\sum_{\begin{subarray}{c}R\text{ s.t. }A_{R}=A,B_{R}=B\\\
\exists\varphi:V(\alpha)\rightarrow[n]:\\\ \varphi\text{ is
injective},\varphi(\alpha)=R\end{subarray}}{\chi_{E_{R}}}$

In other words, $M_{\alpha}=\sum_{R}M_{R}$ where the sum is over ribbons $R$
which can be obtained by assigning each vertex in $V(\alpha)$ a label from
$[n]$.

For examples of graph matrices, see [AMP20].

######  Remark 3.7.

As noted in [AMP20], we index graph matrices by tuples rather than sets so
that they are symmetric (as a function of the input) under permutations of
$[n]$.

###  3.2 Factoring Graph Matrices and Decomposing Shapes into Left, Middle,
and Right Parts

A crucial idea in our analysis is the idea from [BHK+16] of decomposing each
shape $\alpha$ into left, middle, and right parts. This will allow us to give
an approximate factorization of each graph matrix $M_{\alpha}$.

####  3.2.1 Leftmost and Rightmost Minimum Vertex Separators and Decomposition
of Shapes into Left, Middle, and Right Parts

For each shape $\alpha$ we will identify three other shapes, which we denote
by $\sigma,\tau,{\sigma^{\prime}}^{T}$ and call (for reasons we will see soon)
the _left, middle, and right parts of $\alpha$_, respectively. The idea is
that $M_{\alpha}\approx M_{\sigma}M_{\tau}M_{{\sigma^{\prime}}^{T}}$. We
obtain $\sigma,\tau$, and ${\sigma^{\prime}}^{T}$ by splitting the shape
$\alpha$ along the _leftmost and rightmost minimum vertex separators_.

######  Definition 3.8 (Vertex Separators).

We say that a set of vertices $S$ is a vertex separator of $\alpha$ if every
path from $U_{\alpha}$ to $V_{\alpha}$ in $\alpha$ (including paths of length
$0$) intersects $S$. Note that for any vertex separator $S$, $U_{\alpha}\cap
V_{\alpha}\subseteq S$.

######  Definition 3.9 (Minimum Vertex Separators).

We say that $S$ is a minimum vertex separator of $\alpha$ if $S$ is a vertex
separator of $\alpha$ and for any other vertex separator $S^{\prime}$ of
$\alpha$, $|S|\leq|S^{\prime}|$.

######  Definition 3.10 (Leftmost and Rightmost Minimum Vertex Separators).

  1. 1.

We say that $S$ is the leftmost minimum vertex separator of $\alpha$ if $S$ is
a minimum vertex separator of $\alpha$ and for every other minimum vertex
separator $S^{\prime}$ of $\alpha$, every path from $U_{\alpha}$ to
$S^{\prime}$ intersects $S$.

  2. 2.

We say that $T$ is the rightmost minimum vertex separator of $\alpha$ if $T$
is a minimum vertex separator of $\alpha$ and for every other minimum vertex
separator $S^{\prime}$ of $\alpha$, every path from $S^{\prime}$ to
$V_{\alpha}$ intersects $T$.

It is not immediately obvious that leftmost and rightmost minimum vertex
separators are well-defined. For the simplified setting we are considering
here, this was shown by [BHK+16]. We give a more general proof in Appendix A.

We now describe how to split $\alpha$ into left, middle, and right parts
$\sigma,\tau$, and ${\sigma^{\prime}}^{T}$.

######  Definition 3.11 (Decomposition Into Left, Middle, and Right Parts).

Let $\alpha$ be a shape and let $S$ and $T$ be the leftmost and rightmost
minimum vertex separators of $\alpha$. Given orderings $O_{S}$ and $O_{T}$ for
$S$ and $T$, we decompose $\alpha$ into left, middle, and right parts
$\sigma$, $\tau$, and ${\sigma^{\prime}}^{T}$ as follows.

  1. 1.

The left part $\sigma$ of $\alpha$ is the part of $\alpha$ reachable from
$U_{\alpha}$ without passing through $S$. It includes $S$ but excludes all
edges which are entirely within $S$. More formally,

    1. (a)

$V(\sigma)=\\{u\in V(\alpha):\text{ there is a path }P\text{ from
}U_{\alpha}\text{ to }u\text{ in }\alpha\text{ such that
}(V(P)\setminus\\{u\\})\cap S=\emptyset\\}$

    2. (b)

$U_{\sigma}=U_{\alpha}$ and $V_{\sigma}=S$ with the ordering $O_{S}$

    3. (c)

$E(\sigma)=\\{\\{u,v\\}\in E(\alpha):u,v\in V(\sigma),u\notin S\text{ or
}v\notin S\\}$

  2. 2.

The right part ${\sigma^{\prime}}^{T}$ of $\alpha$ is the part of $\alpha$
reachable from $V_{\alpha}$ without intersecting $T$ more than once. It
includes $T$ but excludes all edges which are entirely within $T$. More
formally,

    1. (a)

$V({\sigma^{\prime}}^{T})=\\{u\in V(\alpha):\text{ there is a path }P\text{
from }V_{\alpha}\text{ to }u\text{ in }\alpha\text{ such that
}(V(P)\setminus\\{u\\})\cap T=\emptyset\\}$

    2. (b)

$U_{{\sigma^{\prime}}^{T}}=T$ with the ordering $O_{T}$ and
$V_{{\sigma^{\prime}}^{T}}=V_{\alpha}$.

    3. (c)

$E({\sigma^{\prime}}^{T})=\\{\\{u,v\\}\in E(\alpha):u,v\in
V({\sigma^{\prime}}^{T}),u\notin T\text{ or }v\notin T\\}$

  3. 3.

The middle part $\tau$ of $\alpha$ is, informally, the part of $\alpha$
between $S$ and $T$ (including $S$ and $T$ and all edges which are entirely
within $S$ or within $T$). More formally, let $U_{\tau}=S$ with the ordering
$O_{S}$, let $V_{\tau}=T$ with the ordering $O_{T}$, and let
$E(\tau)=E(\alpha)\setminus(E(\sigma)\cup E(\sigma^{\prime}))$ be all of the
edges of $E(\alpha)$ which do not appear in $E(\sigma)$ or
$E(\sigma^{\prime})$. Then $V(\tau)$ is all of the vertices incident to edges
in $E(\tau)$ together with $S,T$.

######  Remark 3.12.

Note that the decomposition into left, middle, and right parts depends on the
ordering for the vertices in $S$ and $T$. As we will discuss later (see
Section 7.8), we will use all possible orderings simultaneously and then scale
things by an appropriate constant.

Because of the minimality and leftmost/rightmost-ness of the vertex separators
$S,T$ used to define $\sigma,\tau,\sigma^{\prime}$, the shapes
$\sigma,\tau,\sigma^{\prime}$ have some special combinatorial structure, which
we capture in the following proposition. We defer the proof until Section 7
where we state a generalized version.

######  Proposition 3.13.

$\sigma$, $\tau$, and ${\sigma^{\prime}}^{T}$ have the following properties:

  1. 1.

$V_{\sigma}=S$ is the unique minimum vertex separator of $\sigma$.

  2. 2.

$S$ and $T$ are the leftmost and rightmost minimum vertex separators of
$\tau$.

  3. 3.

$T=U_{{\sigma^{\prime}}^{T}}$ is the unique minimum vertex separator of
${\sigma^{\prime}}^{T}$.

Based on this, we define sets of shapes which can appear as left, middle, or
right parts.

######  Definition 3.14 (Left, Middle, and Right Parts).

Let $\alpha$ be a shape.

  1. 1.

We say that $\alpha$ is a left part if $V_{\alpha}$ is the unique minimum
vertex separator of $\alpha$ and $E(\alpha)$ has no edges which are entirely
contained in $V_{\alpha}$.

  2. 2.

We say that $\alpha$ is a proper middle part if $U_{\alpha}$ is the leftmost
minimum vertex separator of $\alpha$ and $V_{\alpha}$ is the rightmost minimum
vertex separator of $\alpha$

  3. 3.

We say that $\alpha$ is a right part if $U_{\alpha}$ is the unique minimum
vertex separator of $\alpha$ and $E(\alpha)$ has no edges which are entirely
contained in $U_{\alpha}$.

######  Remark 3.15.

For technical reasons, later on we will need to consider improper middle parts
$\tau$ where $U_{\tau}$ and $V_{\tau}$ are not the leftmost and rightmost
minimum vertex separators of $\tau$, which is why we make this distinction
here.

The following proposition is also straightforward from the definitions.

######  Proposition 3.16.

A shape $\sigma$ is a left part if and only if $\sigma^{T}$ is a right part

####  3.2.2 Products of Graph Matrices

We now analyze what happens when we take the products of graph matrices.
Roughly speaking, we will have that if $\alpha$ can be decomposed into left,
middle, and right parts $\sigma$, $\tau$, and ${\sigma^{\prime}}^{T}$ then
$M_{\alpha}\approx M_{\sigma}M_{\tau}M_{{\sigma^{\prime}}^{T}}$. However, this
is only an approximation rather than an equality, and this will be the source
of considerable technical difficulties.

We begin with a concatenation operation on ribbons.

######  Definition 3.17 (Ribbon Concatenation).

If $R_{1}$ and $R_{2}$ are two ribbons such that $V(R_{1})\cap
V(R_{2})=B_{R_{1}}=A_{R_{2}}$ and either $R_{1}$ or $R_{2}$ contains no edges
entirely within $B_{R_{1}}=A_{R_{2}}$ then we define $R_{1}\circ R_{2}$ to be
the ribbon formed by glueing together $R_{1}$ and $R_{2}$ along
$B_{R_{1}}=A_{R_{2}}$. In other words,

  1. 1.

$V(R_{1}\circ R_{2})=V(R_{1})\cup V(R_{2})$

  2. 2.

$E(R_{1}\circ R_{2})=E(R_{1})\cup E(R_{2})$

  3. 3.

$A_{R_{1}\circ R_{2}}=A_{R_{1}}$ and $B_{R_{1}\circ R_{2}}=B_{R_{2}}$.

The following proposition is easy to check.

######  Proposition 3.18.

Whenever $R_{1},R_{2}$ are ribbons such that $R_{1}\circ R_{2}$ is defined,
$M_{R_{1}}M_{R_{2}}=M_{R_{1}\circ R_{2}}$

We have an analogous definition for concatenating shapes:

######  Definition 3.19 (Shape Concatenation).

If $\alpha_{1}$ and $\alpha_{2}$ are two shapes such that $V(\alpha_{1})\cap
V(\alpha_{2})=V_{\alpha_{1}}=U_{\alpha_{2}}$ and either $\alpha_{1}$ or
$\alpha_{2}$ contains no edges entirely within $V_{\alpha_{1}}=U_{\alpha_{2}}$
then we define $\alpha_{1}\circ\alpha_{2}$ to be the shape formed by glueing
together $\alpha_{1}$ and $\alpha_{2}$ along $V_{\alpha_{1}}=U_{\alpha_{2}}$.
In other words,

  1. 1.

$V(\alpha_{1}\circ\alpha_{2})=V(\alpha_{1})\cup V(\alpha_{2})$

  2. 2.

$E(\alpha_{1}\circ\alpha_{2})=E(\alpha_{1})\cup E(\alpha_{2})$

  3. 3.

$U_{\alpha_{1}\circ\alpha_{2}}=U_{\alpha_{1}}$ and
$V_{\alpha_{1}\circ\alpha_{2}}=V_{\alpha_{2}}$.

The next proposition, again easy to check, shows that the shape concatenation
operation respects the left/middle/right part decomposition.

######  Proposition 3.20.

If $\alpha$ can be decomposed into left, middle, and right parts
$\sigma,\tau,{\sigma^{\prime}}^{T}$ then
$\alpha=\sigma\circ\tau\circ{\sigma^{\prime}}^{T}$.

We now discuss why
$M_{\alpha}=M_{\sigma\circ\tau\circ{\sigma^{\prime}}^{T}}\approx
M_{\sigma}M_{\tau}M_{{\sigma^{\prime}}^{T}}$ is only an approximation rather
than an equality. Consider the difference
$M_{\sigma}M_{\tau}M_{{\sigma^{\prime}}^{T}}-M_{\sigma\circ\tau\circ{\sigma^{\prime}}^{T}}$.
The graph matrix $M_{\sigma\circ\tau\circ{\sigma^{\prime}}^{T}}$ decomposes
(by definition) into a sum over injective maps
$\varphi\,:\,V(\sigma\circ\tau\circ{\sigma^{\prime}}^{T})\rightarrow[n]$. Also
by expanding definitions, the product
$M_{\sigma}M_{\tau}M_{{\sigma^{\prime}}^{T}}$ expands into a sum over triples
of injective maps $(\varphi_{1},\varphi_{2},\varphi_{3})$, where
$\varphi_{1}\,:\,V(\sigma)\rightarrow[n],\varphi_{2}\,:\,V(\tau)\rightarrow[n],\varphi_{3}\,:\,V(\sigma^{\prime})\rightarrow[n]$
where $\varphi_{1}$ and $\varphi_{2}$ agree on $V_{\sigma}=U_{\tau}$ and
$\varphi_{2}$ and $\varphi_{3}$ agree on $V_{\tau}=U_{{\sigma^{\prime}}^{T}}$.

If they are combined into one map
$\varphi:V(\sigma\cup\tau\cup{\sigma^{\prime}})\rightarrow[n]$, the resulting
$\varphi$ may not be injective because
$\varphi_{1}(V(\sigma)),\varphi_{2}(V(\tau)),\varphi_{3}(V({\sigma^{\prime}}^{T}))$
may have nontrivial intersection (beyond $\varphi_{1}(V_{\sigma})$ and
$\varphi_{2}(V_{\tau})$). We call the resulting terms _intersection terms_ and
handling them properly is a major part of the technical analysis.

######  Remark 3.21.

Actually, the approximation
$M_{\alpha}=M_{\sigma\circ\tau\circ{\sigma^{\prime}}^{T}}\approx
M_{\sigma}M_{\tau}M_{{\sigma^{\prime}}^{T}}$ is also off by a multiplicative
constant because there is also a subtle issue involving the automorphism
groups of these shapes. For now, we ignore this issue. For details about this
issue, see Lemma 7.78.

###  3.3 Shape Coefficient Matrices

The idea for our analysis is as follows. Given a matrix-valued function
$\Lambda$ which is symmetric under permutations of $[n]$, we write
$\Lambda=\sum_{\alpha}{\lambda_{\alpha}M_{\alpha}}$. We then break each shape
$\alpha$ up into left, middle, and right parts $\sigma$, $\tau$, and
${\sigma^{\prime}}^{T}$.

For this analysis, we use _shape coefficient matrices_ $H_{\tau}$ whose rows
and columns are indexed by left shapes and whose entries depend on the
coefficients $\lambda_{\alpha}$. We choose these matrices so that

$\Lambda=\sum_{\tau}{H_{\tau}(\sigma,\sigma^{\prime})M_{\sigma\circ\tau\circ{\sigma^{\prime}}^{T}}}\approx\sum_{\tau}{H_{\tau}(\sigma,\sigma^{\prime})M_{\sigma}M_{\tau}M_{{\sigma^{\prime}}^{T}}}$

To set this up, we separate the possible middle parts $\tau$ into groups based
on the size of $U_{\tau}$ and whether or not they are trivial.

######  Definition 3.22.

We define $\mathcal{I}_{mid}$ to be the set of all possible $U_{\tau}$. Here
$\mathcal{I}_{mid}$ is the set of tuples of unspecified vertices of the form
$U=(u_{1},\ldots,u_{k})$ where $0\leq k\leq d$.

######  Definition 3.23.

We say that a proper middle shape $\tau$ is trivial if $E(\tau)=\emptyset$ and
$|U_{\tau}\cap V_{\tau}|=|U_{\tau}|=|V_{\tau}|$ (i.e. $V_{\tau}$ is a
permutation of $U_{\tau}$).

For simplicity, the only proper trivial middle parts $\tau$ we consider are
shapes $Id_{U}$ corresponding to identity matrices.

######  Definition 3.24.

Given a tuple of unspecified vertices $U=(u_{1},\ldots,u_{|U|})$ We define
$Id_{U}$ to be the shape where $V(Id_{U})=U$, $U_{Id_{U}}=V_{Id_{U}}=U$, and
$E(Id_{U})=\emptyset$.

We group all of the proper non-trivial middle parts $\tau$ into sets
$\mathcal{M}_{U}$ based on the size of $U_{\tau}$.

######  Definition 3.25.

Given a tuple of unspecified vertices $U=(u_{1},\ldots,u_{|U|})$, we define
$\mathcal{M}_{U}$ to be the set of proper non-trivial middle parts $\tau$ such
that $U_{\tau}$ and $V_{\tau}$ have the same size as $U$. Note that $U_{\tau}$
and $V_{\tau}$ may intersect each other arbitrarily.

With these definitions, we can now define our shape coefficient matrices.

######  Definition 3.26.

Given $U\in\mathcal{I}_{mid}$, we define $\mathcal{L}_{U}$ to be the set of
left shapes $\sigma$ such that $|V_{\sigma}|=|U|$.

######  Definition 3.27.

For each $U\in\mathcal{I}_{mid}$, we define the shape coefficient matrix
$H_{Id_{U}}$ to be the matrix indexed by left shapes
$\sigma,\sigma^{\prime}\in\mathcal{L}_{U}$ with entries
$H_{Id_{U}}(\sigma,\sigma^{\prime})=\frac{1}{|U|!}\lambda_{\sigma\circ{\sigma^{\prime}}^{T}}$

######  Definition 3.28.

For each $U\in\mathcal{I}_{mid}$, for each $\tau\in\mathcal{M}_{U}$, we define
the shape coefficient matrix $H_{\tau}$ to be the matrix indexed by left
shapes $\sigma,\sigma^{\prime}\in\mathcal{L}_{U}$ with entries
$H_{\tau}(\sigma,\sigma^{\prime})=\frac{1}{(|U|!)^{2}}\lambda_{\sigma\circ\tau\circ{\sigma^{\prime}}^{T}}$

With these shape coefficient matrices, we have the following decomposition of
$\Lambda=\sum_{\alpha}{\lambda_{\alpha}M_{\alpha}}$.

######  Lemma 3.29.

$\Lambda=\sum_{U\in\mathcal{I}_{mid}}{\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}_{U}}{H_{Id_{U}}(\sigma,\sigma^{\prime})M_{\sigma\circ{\sigma^{\prime}}^{T}}}}+\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}_{U}}{H_{\tau}(\sigma,\sigma^{\prime})M_{\sigma\circ\tau\circ{\sigma^{\prime}}^{T}}}}}$

We defer the proof of this lemma to Lemma 7.81.

For technical reasons, we need to define one more operation to handle
intersection terms. We call this operation _the $-\gamma,\gamma$ operation._

######  Definition 3.30.

Given $U,V\in\mathcal{I}_{mid}$ where $|U|>|V|$, we define $\Gamma_{U,V}$ to
be the set of left parts $\gamma$ such that $|U_{\gamma}|=|U|$ and
$V_{\gamma}=|V|$.

######  Definition 3.31.

Given $U,V\in\mathcal{I}_{mid}$ where $|U|>|V|$, a shape coefficient matrix
$H_{Id_{V}}$, and a $\gamma\in\Gamma_{U,V}$, we define the shape coefficient
matrix $H^{-\gamma,\gamma}_{Id_{V}}$ to be the matrix indexed by left shapes
$\sigma,\sigma^{\prime}\in\mathcal{L}_{U}$ with entries
$H^{-\gamma,\gamma}_{Id_{V}}(\sigma,\sigma^{\prime})=H(\sigma\circ\gamma,\sigma^{\prime}\circ\gamma)$

###  3.4 Informal Theorem Statement

We are now ready to state a simplified, qualitative version of our main
theorem. For the full, quantitative version of our main theorem, see Theorem
7.101.

######  Theorem 3.32.

There exist functions $f(\tau):\mathcal{M}_{U}\rightarrow{\mathbb{R}}$ and
$f(\gamma):\Gamma_{U,V}\rightarrow{\mathbb{R}}$ depending on $n$ and other
parameters such that if $\Lambda=\sum_{\alpha}{\lambda_{\alpha}M_{\alpha}}$
and the following conditions hold:

  1. 1.

For all $U\in\mathcal{I}_{mid}$, $H_{Id_{U}}\succeq 0$

  2. 2.

For all $U\in\mathcal{I}_{mid}$ and all $\tau\in\mathcal{M}_{U}$,

$\left[{\begin{array}[]{cc}H_{Id_{U}}&f(\tau)H_{\tau}\\\
f(\tau)H^{T}_{\tau}&H_{Id_{U}}\end{array}}\right]\succeq 0$

  3. 3.

For all $U,V\in\mathcal{I}_{mid}$ such that $|U|>|V|$ and all
$\gamma\in\Gamma_{U,V}$, $H^{-\gamma,\gamma}_{Id_{V_{\gamma}}}\preceq
f(\gamma)H_{Id_{U_{\gamma}}}$

then with probability at least $1-o(1)$ over $G\sim\\{\pm 1\\}^{n\choose 2}$
it holds that $\Lambda(G)\succeq 0$.

######  Remark 3.33.

As we will demonstrate in the remainder of this paper, our machinery works
well when the coefficients $\lambda_{\alpha}$ for each shape have an
exponential decay in both $|V(\alpha)|$ and $|E(\alpha)|$. However, since our
machinery is highly technical with many different parts, it does not work as
well if the coefficients have a different kind of decay.

###  3.5 An informal application to planted clique

Before we move on to further definitions needed for a more complete statement
of the main theorem, we present an informal example.

######  Example 3.34.

When the pseudo-calibration method is applied to prove an SoS lower bound for
the planted clique problem in $n$ node graphs with clique size $k$, as in
[BHK+16], the matrix-valued function which results is
$\Lambda=\sum_{\alpha\,:\,|V(\alpha)|\leq
t}{\left(\frac{k}{n}\right)^{|V(\alpha)|}M_{\alpha}}$ where $t\approx\log(n)$.
One may then compute that the matrices $H_{Id_{U}}$ and $H_{\tau}$ are as
follows (at least so long as $|V(\sigma)|,|V(\tau)|,|V(\sigma^{\prime})|\ll
t$; we ignore this detail for now). For all $r\in[0,\frac{d}{2}]$,

  1. 1.

For $U$ with $|U|=r$,
$H_{Id_{U}}(\sigma,\sigma^{\prime})=\left(\frac{k}{n}\right)^{|V(\sigma)|+|V(\sigma^{\prime})|-r}$

  2. 2.

For all proper, non-trivial middle shapes $\tau$ such that
$|U_{\tau}|=|V_{\tau}|=r$,

$H_{\tau}(\sigma,\sigma^{\prime})=\left(\frac{k}{n}\right)^{|V(\sigma)|+|V(\sigma^{\prime})|+|V(\tau)|-2r}$

Defining $v_{r}$ to be the vector such that
$v_{r}(\sigma)=\left(\frac{k}{n}\right)^{|V(\sigma)|-\frac{r}{2}}$, we have
that

  1. 1.

For $U$ with $|U|=r$, $H_{Id_{U}}={v_{|U|}}{v^{T}_{|U|}}$

  2. 2.

For all proper, non-trivial middle shapes $\tau$ such that
$|U_{\tau}|=|V_{\tau}|=r$,
$H_{\tau}=\left(\frac{k}{n}\right)^{|V(\tau)|-r}{v_{r}}{v^{T}_{r}}$

  3. 3.

For all left parts $\gamma$,
$H^{-\gamma,\gamma}_{Id_{V_{\gamma}}}=\left(\frac{k}{n}\right)^{2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|}v_{|U_{\gamma}|}v^{T}_{|U_{\gamma}|}$

It turns out in this setting that we can take $f(\tau)$ to be
$\tilde{O}(n^{\frac{|V(\tau)|-|U_{\tau}|}{2}})$ and $f(\gamma)$ to be
$\tilde{O}(n^{|V(\gamma)\setminus U_{\gamma}|})$. Thus, as long as
$k\ll\sqrt{n}$,

  1. 1.

For any $U$ and all $\tau$ such that $V_{\tau}\neq U_{\tau}$ with
$|U_{\tau}|=|V_{\tau}|=|U|$, $f(\tau)H_{\tau}\preceq H_{Id_{U}}$.

  2. 2.

For all non-trivial left parts $\gamma$,
$H^{-\gamma,\gamma}_{Id_{V_{\gamma}}}\preceq f(\gamma)H_{Id_{U_{\gamma}}}$

######  Remark 3.35.

This does not quite satisfy the conditions of Theorem 3.32 because there are
$\tau$ such that $V_{\tau}=U_{\tau}$ but which are non-trivial because
$E(\tau)\neq\emptyset$. For these $\tau$, condition 2 of Theorem 3.32 fails.

In order to prove their SoS lower bounds for planted clique, [BHK+16] handle
this issue by grouping together all of the $\tau$ where $V_{\tau}=U_{\tau}$
into the indicator function for whether $V_{\tau}=U_{\tau}$ is a clique.

In this paper, we get around this issue by instead considering the planted
slightly denser subgraph problem. This introduces an edge decay into the
coefficients. For details, see Section 4.

###  3.6 Generalizing the machinery

In this section, we restricted ourselves to the case when the
$\\{-1,1\\}^{\binom{n}{2}}$ for simplicity. However, for our results we will
need to handle more general types of inputs. We now briefly describe which
kinds of inputs we will need to handle and how we handle them.

  1. 1.

In general, the entries of the input may be labeled by more than $2$ indices.
For example, for tensor PCA on order $3$ tensors, the entries of the input are
indexed by $3$ indices. To handle this, we will have shapes which have
hyperedges rather than edges.

  2. 2.

In general, the entries of the input will come from a distribution $\Omega$
rather than being $\pm{1}$. To handle this, we will take an orthonormal basis
$\\{h_{k}\\}$ for $\Omega$. We will then give each edge/hyperedge a label $l$
to specify which polynomial $h_{l}$ should be applied to that entry of the
input.

  3. 3.

In general, there may be $t$ different types of indices rather than just one
type of index. In this case, the symmetry group will be
$S_{n_{1}}\times\ldots\times S_{n_{t}}$ rather than $S_{n}$. To handle this,
we will have shapes with different types of vertices.

We formally make these generalizations in Section 7.

###  3.7 Further definitions needed for our applications

We will describe some more notations and definitions that will be useful to us
to describe the qualitative bounds for our applications. For each of our
applications, we will describe the corresponding modifications needed to the
definitions already in place and present new definitions where necessary.

####  3.7.1 Planted slightly denser subgraph

Since the input is a graph $G\in\\{-1,1\\}^{\binom{[n]}{2}}$, most of what we
introduced already apply to this setting. To describe the moment matrix, we
need to define the truncation parameter.

######  Definition 3.36 (Truncation parameters).

For integers $D_{sos},D_{V}\geq 0$, say that a shape $\alpha$ satisfies the
truncation parameters $D_{sos},D_{V}$ if

  * -

The degrees of the monomials that $U_{\alpha}$ and $V_{\alpha}$ correspond to,
are at most $\frac{D_{sos}}{2}$

  * -

The left part $\sigma$, the middle part $\tau$ and the right part
$\sigma^{\prime}$ of $\alpha$ satisfy
$|V(\sigma)|,|V(\tau)|,|V(\sigma^{\prime})|\leq D_{V}$

####  3.7.2 Tensor PCA

We consider the input to be a tensor $A\in\mathbb{R}^{[n]^{k}}$. The input
entries are now sampled from the distribution $\mathcal{N}(0,1)$ instead of
$\\{-1,1\\}$. So, we will work with the Hermite basis of polynomials.

Let the standard unnormalized Hermite polynomials be denoted as
$h_{0}(x)=1,h_{1}(x)=x,h_{2}(x)=x^{2}-1,\ldots$. Then, we work with the basis
$h_{a}(A):=\prod_{e\in[n]^{k}}h_{e}(A_{e})$ over $a\in\mathbb{N}^{[n]^{k}}$.
Accordingly, we will modify the graphs that represent ribbons (and by
extension, shapes), to have labeled hyperedges of arity $k$. So, an hyperedge
$e$ with a label $t$ will correspond to the hermite polynomial $h_{t}(A_{e})$.

######  Definition 3.37 (Hyperedges).

Instead of standard edges, we will have labeled hyperedges of arity $k$ in the
underlying graphs for our ribbons as well as shapes. The label for an
hyperedge $e$, denoted $l_{e}$, is an element of $\mathbb{N}$ which will
correspond to the Hermite polynomial being evaluated on that entry.

Note that our hyperedges are ordered since the tensor $A$ is not necessarily
symmetric.

For variables $x_{1},\ldots,x_{n}$, the rows and columns of our moment matrix
will now correspond to monomials of the form $\prod_{i\leq n}x_{i}^{p_{i}}$
for $p_{i}\geq 0$. To capture this, we use the notion of index shape pieces
and index shapes. Informally, we split the above monomial product into groups
based on their powers and each such group will form an index shape piece.

######  Definition 3.38 (Index shape piece).

An index shape piece $U_{i}=((U_{i,1},\ldots,U_{i,t}),p_{i})$ is a tuple of
indices $(U_{i,1},\ldots,U_{i,t})$ along with a power $p_{i}\in\mathbb{N}$.
Let $V(U_{i})$ be the set $\\{U_{i,1},\ldots,U_{i,t}\\}$ of vertices of this
index shape piece. When clear from context, we use $U_{i}$ instead of
$V(U_{i})$.

If we realize $U_{i,1},\ldots,U_{i,t}$ to be indices
$a_{1},\ldots,a_{t}\in[n]$, then, this realization of this index shape piece
corresponds to the monomial $\prod_{j\leq t}x_{a_{j}}^{p_{i}}$.

######  Definition 3.39 (Index shape).

An index shape $U$ is a set of index shape pieces $U_{i}$ that have different
powers. Let $V(U)$ be the set of vertices $\cup_{i}V(U_{i})$. When clear from
context, we use $U$ instead of $V(U)$.

Observe that each realization of an index shape corresponds to a row or column
of the moment matrix.

######  Definition 3.40.

For two index shapes $U,V$, we write $U\equiv V$ if for all powers $p$, the
index shape pieces of power $p$ in $U$ and $V$ have the same length.

######  Definition 3.41.

Define ${\mathcal{I}}_{mid}$ to be the set of all index shapes $U$ that
contain only index shape pieces of power $1$.

In the definition of shapes, the distinguished set of vertices should now be
replaced by index shapes.

######  Definition 3.42 (Shapes).

Shapes are tuples $\alpha=(H_{\alpha},U_{\alpha},V_{\alpha})$ where
$H_{\alpha}$ is a graph with hyperedges of arity $k$ and
$U_{\alpha},V_{\alpha}$ are index shapes such that
$U_{\alpha},V_{\alpha}\subseteq V(H_{\alpha})$.

######  Definition 3.43 (Proper shape).

A shape $\alpha$ is proper if it has no isolated vertices outside
$U_{\alpha}\cup V_{\alpha}$, no multi-edges and all the edges have a nonzero
label.

To define the notion of vertex separators, we modify the notion of paths for
hyperedges.

######  Definition 3.44 (Path).

A path is a sequence of vertices $u_{1},\ldots,u_{t}$ such that
$u_{i},u_{i+1}$ are in the same hyperedge, for all $i\leq t-1$.

The notions of vertex separator and decomposition into left, middle and right
parts are identically defined with the above notion of hyperedges and paths.
In Section 7, we will show that they are well defined.

In the definition of trivial shape $\tau$, we now require $U_{\tau}\equiv
V_{\tau}$. For $U\in{\mathcal{I}}_{mid}$, ${\mathcal{M}}_{U}$ will be the set
of proper non-trivial middle parts $\tau$ with $U_{\tau}\equiv V_{\tau}\equiv
U$ and ${\mathcal{L}}_{U}$ will be the set of left parts $\sigma$ such that
$V_{\sigma}\equiv U$. Similarly, for $U,V\in{\mathcal{I}}_{mid}$,
${\mathcal{L}}_{U,V}$ will be the set of left parts $\gamma$ such that
$U_{\gamma}\equiv U$ and $V_{\gamma}\equiv V$.

In order to define the moment matrix, we need to truncate our shapes based on
the number of vertices and the labels on our hyperedges. So, we make the
following definition.

######  Definition 3.45 (Truncation parameters).

For integers $D_{sos},D_{V},D_{E}\geq 0$, say that a shape $\alpha$ satisfies
the truncation parameters $D_{sos},D_{V},D_{E}$ if

  * -

The degrees of the monomials that $U_{\alpha}$ and $V_{\alpha}$ correspond to,
are at most $\frac{D_{sos}}{2}$

  * -

The left part $\sigma$, the middle part $\tau$ and the right part
$\sigma^{\prime T}$ of $\alpha$ satisfy
$|V(\sigma)|,|V(\tau)|,|V(\sigma^{\prime T})|\leq D_{V}$

  * -

For each $e\in E(\alpha)$, $l_{e}\leq D_{E}$.

####  3.7.3 Sparse PCA

We consider the $m$ vectors $v_{1},\ldots,v_{m}\in\mathbb{R}^{d}$ to be the
input. Similar to Tensor PCA, we will work with the Hermite basis of
polynomials since the entries are sampled from the distribution
$\mathcal{N}(0,1)$.

In particular, if we denote the unnormalized Hermite polynomials by
$h_{0}(x)=1,h_{1}(x)=x,h_{2}(x)=x^{2}-1,\ldots$, then, we work with the basis
$h_{a}(v):=\prod_{i\in[m],j\in[n]}h_{a_{i,j}}(v_{i,j})$ over
$a\in\mathbb{N}^{m\times n}$. To capture these bases, we will modify the
graphs that represent ribbons (and by extension, shapes), to be bipartite
graphs with two types of vertices, and have labeled edges that go across
vertices of different types. So, an edge $(i,j)$ with label $t$ between a
vertex $i$ of type $1$ and a vertex $j$ of type $2$ will correspond to
$h_{t}(v_{i,j})$.

######  Definition 3.46 (Vertices).

We will have two types of vertices, the vertices corresponding to the $m$
input vectors that we call type $1$ vertices and the vertices corresponding to
ambient dimension of the space that we call type $2$ vertices.

######  Definition 3.47 (Edges).

Edges will go across vertices of different types, thereby forming a bipartite
graph. An edge between a type $1$ vertex $i$ and a type 2 vertex $j$
corresonds to the input entry $v_{i,j}$. Each edge will have a label in
$\mathbb{N}$ corresponding to the Hermite polynomial evaluated on that entry.

We will have variables $x_{1},\ldots,x_{n}$ in our SoS program, so we will
work with index shape pieces and index shapes as in Tensor PCA, since the rows
and columns of our moment matrix will now correspond to monomials of the form
$\prod_{i\leq n}x_{i}^{p_{i}}$ for $p_{i}\geq 0$. But since in our
decompositions into left, right and middle parts, we will have type $2$
vertices as well in the vertex separators, we will define a generalized notion
of index shape pieces and index shapes.

######  Definition 3.48 (Index shape piece).

An index shape piece $U_{i}=((U_{i,1},\ldots,U_{i,t}),t_{i},p_{i})$ is a tuple
of indices $(U_{i,1},\ldots,U_{i,t})$ along a type $t_{i}\in\\{1,2\\}$ with a
power $p_{i}\in\mathbb{N}$. Let $V(U_{i})$ be the set
$\\{U_{i,1},\ldots,U_{i,t}\\}$ of vertices of this index shape piece. When
clear from context, we use $U_{i}$ instead of $V(U_{i})$.

For an index shape piece $((U_{i,1},\ldots,U_{i,t}),t_{i},p_{i})$ with type
$t_{i}=2$, if we realize $U_{i_{1}},\ldots,U_{i_{t}}$ to be indices
$a_{1},\ldots,a_{t}\in[n]$, then, this index shape pieces correspond this to
the monomial $\prod_{j\leq n}x_{a_{j}}^{p_{i}}$.

######  Definition 3.49 (Index shape).

An index shape $U$ is a set of index shape pieces $U_{i}$ that have either
have different types or different powers. Let $V(U)$ be the set of vertices
$\cup_{i}V(U_{i})$. When clear from context, we use $U$ instead of $V(U)$.

Observe that each realization of an index shape corresponds to a row or column
of the moment matrix. For our moment matrix, the only nonzero rows correspond
to index shapes that have only index shape pieces of type $2$, since the only
SoS variables are $x_{1}\ldots,x_{n}$, but in order to do our analysis, we
need to work with the generalized notion of index shapes that allow index
shape pieces of both types.

######  Definition 3.50.

For two index shapes $U,V$, we write $U\equiv V$ if for all types $t$ and all
powers $p$, the index shape pieces of type $t$ and power $p$ in $U$ and $V$
have the same length.

######  Definition 3.51.

Define ${\mathcal{I}}_{mid}$ to be the set of all index shapes $U$ that
contain only index shape pieces of power $1$.

Since we are working with standard graphs, the notion of path and vertex
separator need no modifications, but we will now use the minimum weight vertex
separator instead of the minimum vertex separator where we define the weight
as follows.

######  Definition 3.52 (Weight of an index shape).

Suppose we have an index shape $U=\\{U_{1},U_{2}\\}\in{\mathcal{I}}_{mid}$
where $U_{1}=((U_{1,1},\ldots,U_{1,|U_{1}|}),1,1)$ is an index shape piece of
type $1$ and $U_{2}=((U_{2,1},\ldots,U_{2,|U_{2}|}),2,1)$ is an index shape
piece of type $2$. Then, define the weight of this index shape to be
$w(U)=\sqrt{m}^{|U_{1}|}\sqrt{n}^{|U_{2}|}$.

We now give the modified definition of shapes.

######  Definition 3.53 (Shapes).

Shapes are tuples $\alpha=(H_{\alpha},U_{\alpha},V_{\alpha})$ where
$H_{\alpha}$ is a graph with two types of vertices, has labeled edges only
across vertices of different types and $U_{\alpha},V_{\alpha}$ are index
shapes such that $U_{\alpha},V_{\alpha}\subseteq V(H_{\alpha})$.

######  Definition 3.54 (Proper shape).

A shape $\alpha$ is proper if it has no isolated vertices outside
$U_{\alpha}\cup V_{\alpha}$, no multi-edges and all the edges have a nonzero
label.

In Section 7, we will show that with this new definition of weight and shapes,
any shape $\alpha$ has a unique decomposition into
$\sigma\circ\tau\circ\sigma^{\prime T}$ where $\sigma,\tau,\sigma^{\prime T}$
are left, middle and right parts respectively. Here, $\tau$ may possibly be
improper.

In the definition of trivial shape $\tau$, we now require $U_{\tau}\equiv
V_{\tau}$. For $U\in{\mathcal{I}}_{mid}$, ${\mathcal{M}}_{U}$ will be the set
of proper non-trivial middle parts $\tau$ with $U_{\tau}\equiv V_{\tau}\equiv
U$ and ${\mathcal{L}}_{U}$ will be the set of left parts $\sigma$ such that
$V_{\sigma}\equiv U$. Similarly, for $U,V\in{\mathcal{I}}_{mid}$,
${\mathcal{L}}_{U,V}$ will be the set of left parts $\gamma$ such that
$U_{\gamma}\equiv U$ and $V_{\gamma}\equiv V$.

Finally, in order to define the moment matrix, we need to truncate our shapes
based on the number of vertices and the labels on our edges. So, we make the
following definition.

######  Definition 3.55 (Truncation parameters).

For integers $D_{sos},D_{V},D_{E}\geq 0$, say that a shape $\alpha$ satisfies
the truncation parameters $D_{sos},D_{V},D_{E}$ if

  * -

The degrees of the monomials that $U_{\alpha}$ and $V_{\alpha}$ correspond to,
are at most $\frac{D_{sos}}{2}$

  * -

The left part $\sigma$, the middle part $\tau$ and the right part
$\sigma^{\prime T}$ of $\alpha$ satisfy
$|V(\sigma)|,|V(\tau)|,|V(\sigma^{\prime T})|\leq D_{V}$

  * -

For each $e\in E(\alpha)$, $l_{e}\leq D_{E}$.

####  3.7.4 Relaxing the third condition

In Theorem 3.32, the third qualitative condition we’d like to show is as
follows: For all $U,V\in\mathcal{I}_{mid}$ such that $|U|>|V|$ and all
$\gamma\in\Gamma_{U,V}$, $H^{-\gamma,\gamma}_{Id_{V_{\gamma}}}\preceq
f(\gamma)H_{Id_{U_{\gamma}}}$.

For technical reasons, we won’t be able to show this directly. To handle this,
we instead work with a slight modification of $H_{Id_{U_{\gamma}}}$, a matrix
$H_{\gamma}^{\prime}$ that’s very close to $H_{Id_{U_{\gamma}}}$. So, what we
will end up showing is: For all $U,V\in\mathcal{I}_{mid}$ such that $|U|>|V|$
and all $\gamma\in\Gamma_{U,V}$, $H^{-\gamma,\gamma}_{Id_{V_{\gamma}}}\preceq
f(\gamma)H^{\prime}_{\gamma}$

Let $D_{V}$ be the truncation parameter. A canonical choice for
$H^{\prime}_{\gamma}$ is to take

  1. 1.

$H^{\prime}_{\gamma}(\sigma,\sigma^{\prime})=H_{Id_{U}}(\sigma,\sigma^{\prime})$
whenever $|V(\sigma\circ\gamma)|\leq D_{V}$ and
$|V(\sigma^{\prime}\circ\gamma)|\leq D_{V}$.

  2. 2.

$H^{\prime}_{\gamma}(\sigma,\sigma^{\prime})=0$ whenever
$|V(\sigma\circ\gamma)|>D_{V}$ or $|V(\sigma^{\prime}\circ\gamma)|>D_{V}$.

With this choice, $H_{\gamma}^{\prime}$ is the same as $H_{Id_{U_{\gamma}}}$
upto truncation error. We will formally bound the errors in the quantitative
sections after we introduce the full machinery.

##  4 Qualitative bounds for Planted slightly denser subgraph

###  4.1 Pseudo-calibration

We will pseudo-calibrate with respect the following pair of random and planted
distributions which we denote $\nu$ and $\mu$ respectively.

See 1.1.2

We assume that the input is given as $G_{i,j}$ for $i,j\in\binom{[n]}{2}$
where $G_{i,j}$ is $1$ if the edge $(i,j)$ is present in the graph and $-1$
otherwise. We work with the Fourier basis $\chi_{E}$ defined as
$\chi_{E}(G):=\prod_{(i,j)\in E}G_{i,j}$. For a subset $I\subseteq[n]$, define
$x_{I}:=\prod_{i\in I}x_{I}$.

######  Lemma 4.1.

Let $I\subseteq[n],E\subseteq\binom{[n]}{2}$. Then,

$\mathop{\mathbb{E}}_{\mu}[x_{I}\chi_{E}(G)]=\left(\frac{k}{n}\right)^{|I\cup
V(E)|}(2p-1)^{|E|}$

###### Proof.

When we sample $(G,S)$ from $\mu$, we condition on whether $I\cup
V(E)\subseteq S$.

$\displaystyle\mathop{\mathbb{E}}_{(G,S)\sim\mu}[x_{I}\chi_{E}(G)]$
$\displaystyle=Pr_{(G,S)\sim\mu}[I\cup V(E)\subseteq
S]\mathop{\mathbb{E}}_{(G,S)\sim\mu}[x_{I}\chi_{E}(G)|I\cup V(E)\subseteq S]$
$\displaystyle\qquad+Pr_{(G,S)\sim\mu}[I\cup V(E)\not\subseteq
S]\mathop{\mathbb{E}}_{(G,S)\sim\mu}[x_{I}\chi_{E}(G)|I\cup V(E)\not\subseteq
S]$

We claim that the second term is $0$. In particular,
$\mathop{\mathbb{E}}_{(G,S)\sim\mu}[x_{I}\chi_{E}(G)|I\cup V(E)\not\subseteq
S]=0$ because when $I\cup V(E)\not\subseteq S$, either $S$ doesn’t contain a
vertex in $I$ or an edge $(i,j)\in E$ is outside $S$. If $S$ doesn’t contain a
vertex in $I$, then $x_{I}=0$ and hence, the quantity is $0$. And if an edge
$(i,j)\in E$ is outside $S$, since this edge is sampled with probability
$\frac{1}{2}$, by taking expectations, the quantity
$\mathop{\mathbb{E}}_{(G,S)\sim\mu}[x_{I}\chi_{E}(G)|I\cup V(E)\not\subseteq
S]$ is $0$.

Finally, note that $Pr_{(G,S)\sim\mu}[I\cup V(E)\subseteq
S]=\left(\frac{k}{n}\right)^{|I\cup V(E)|}$ and

$\mathop{\mathbb{E}}_{(G,S)\sim\mu}[x_{I}\chi_{E}(G)|I\cup V(E)\subseteq
S]=\mathop{\mathbb{E}}_{(G,S)\sim\mu}[\chi_{E}(G)|V(E)\subseteq
S]=(2p-1)^{|E|}$

The last equality follows because for each edge $e\in E$, since $e$ is present
independently with probability $p$, the expected value of $\chi_{e}$ is
$1\cdot p+(-1)\cdot(1-p)=2p-1$.

Now, we can write the moment matrix in terms of graph matrices.

######  Definition 4.2.

Define the degree of SoS to be $D_{sos}=n^{C_{sos}\varepsilon}$ for some
constant $C_{sos}>0$ that we choose later.

######  Definition 4.3 (Truncation parameter).

Define the truncation parameter to be $D_{V}=n^{C_{V}\varepsilon}$ for some
constant $C_{V}>0$.

######  Remark 4.4 (Choice of parameters).

We first set $\varepsilon$ to be a sufficiently small constant. Based on this
choice, we will set $C_{V}$ to be a sufficiently small constant to satisfy all
the inequalities we use in our proof. Based on these choices, we can choose
$C_{sos}$ to be sufficiently small to satisfy the inequalities we use.

We will now describe the decomposition of the moment matrix $\Lambda$.

######  Definition 4.5.

If a shape $\alpha$ satisfies the following properties:

  * -

$\alpha$ is proper,

  * -

$\alpha$ satisfies the truncation parameter $D_{sos},D_{V}$.

then define

$\lambda_{\alpha}=\left(\frac{k}{n}\right)^{|V(\alpha)|}(2p-1)^{|E(\alpha)|}$

######  Corollary 4.6.

$\Lambda=\sum\lambda_{\alpha}M_{\alpha}$.

###  4.2 Proving positivity - Qualitative bounds

We use the canonical definition of $H_{\gamma}^{\prime}$ from Section 3.7.4.
In this section, we will prove the main qualitative bounds Lemma 4.7, Lemma
4.9 and Lemma 4.11.

######  Lemma 4.7.

For all $U\in{\mathcal{I}}_{mid}$, $H_{Id_{U}}\succeq 0$

We define the following quantity to capture the contribution of the vertices
within $\tau$ to the Fourier coefficients.

######  Definition 4.8.

For $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, define

$S(\tau)=\left(\frac{k}{n}\right)^{|V(\tau)|-|U_{\tau}|}(2p-1)^{|E(\tau)|}$

######  Lemma 4.9.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$,

$\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}\succeq 0$

We define the following quantity to capture the contribution of the vertices
within $\gamma$ to the Fourier coefficients.

######  Definition 4.10.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and
$\gamma\in\Gamma_{U,V}$, define

$S(\gamma)=\left(\frac{k}{n}\right)^{|V(\gamma)|-\frac{|U_{\gamma}|+|V_{\gamma}|}{2}}(2p-1)^{|E(\gamma)|}$

######  Lemma 4.11.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}}H_{Id_{V}}^{-\gamma,\gamma}\preceq
H_{\gamma}^{\prime}$

In order to prove these bounds, we define the following quantity to capture
the contribution of the vertices within $\sigma$ to the Fourier coefficients.

######  Definition 4.12.

For a shape $\sigma\in{\mathcal{L}}$, define

$T(\sigma)=\left(\frac{k}{n}\right)^{|V(\sigma)|-\frac{|V_{\sigma}|}{2}}(2p-1)^{|E(\sigma)|}$

######  Definition 4.13.

For $U\in{\mathcal{I}}_{mid}$, define $v_{U}$ to be the vector indexed by
$\sigma\in{\mathcal{L}}$ such that $v_{U}(\sigma)=T(\sigma)$ if
$\sigma\in{\mathcal{L}}_{U}$ and $0$ otherwise.

######  Proposition 4.14.

For all $U\in{\mathcal{I}}_{mid},\rho\in{\mathcal{P}}_{U}$,
$H_{Id_{U}}=\frac{1}{|Aut(U)|}v_{U}v_{U}^{T}$.

###### Proof.

This follows by verifying the conditions of Definition 4.5.

This immediately implies that for all $U\in{\mathcal{I}}_{mid}$,
$H_{Id_{U}}\succeq 0$, which is Lemma 4.7.

We restate Definition 4.8 for convenience.

See 4.8

######  Proposition 4.15.

For any $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$,
$H_{\tau}=\frac{1}{|Aut(U)|^{2}}S(\tau)v_{U}v_{U}^{T}$.

###### Proof.

This follows by a straightforward verification of the conditions of Definition
4.5.

Lemma 4.9 immediately follows.

See 4.9

###### Proof.

$\displaystyle\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}v_{U}v_{U}^{T}&\frac{S(\tau)}{|Aut(U)|}v_{U}v_{U}^{T}\\\
\frac{S(\tau)}{|Aut(U)|}v_{U}v_{U}^{T}&\frac{S(\tau)}{|Aut(U)|}v_{U}v_{U}^{T}\end{bmatrix}\succeq
0$

We restate Definition 4.10 for convenience.

See 4.10

######  Proposition 4.16.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, for all
$\gamma\in\Gamma_{U,V}$,

$H_{Id_{V}}^{-\gamma,\gamma}=\frac{|Aut(U)|}{|Aut(V)|}S(\gamma)^{2}H^{\prime}_{\gamma}$

###### Proof.

Fix $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}$ such that
$|V(\sigma\circ\gamma)|,|V(\sigma^{\prime}\circ\gamma)|\leq D_{V}$. Note that
$|V(\sigma)|-\frac{|V_{\sigma}|}{2}+|V(\sigma^{\prime})|-\frac{|V_{\sigma^{\prime}}|}{2}+2(|V(\gamma)|-\frac{|U_{\gamma}|+|V_{\gamma}|}{2})=|V(\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime
T})|$. Using Definition 4.5, we can easily verify that
$\lambda_{\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime
T}}=T(\sigma)T(\sigma^{\prime})S(\gamma)^{2}$. Therefore,
$H_{Id_{V}}^{-\gamma,\gamma}(\sigma,\sigma^{\prime})=\frac{|Aut(U)|}{|Aut(V)|}S(\gamma)^{2}H_{Id_{U}}(\sigma,\sigma^{\prime})$.
Since
$H^{\prime}_{\gamma}(\sigma,\sigma^{\prime})=H_{Id_{U}}(\sigma,\sigma^{\prime})$
whenever $|V(\sigma\circ\gamma)|,|V(\sigma^{\prime}\circ\gamma)|\leq D_{V}$,
this completes the proof.

Rearranging this gives Lemma 4.11

See 4.11

##  5 Qualitative bounds for Tensor PCA

###  5.1 Pseudo-calibration

######  Definition 5.1 (Slack parameter).

Define the slack parameter to be $\Delta=n^{-C_{\Delta}\varepsilon}$ for a
constant $C_{\Delta}>0$.

We will pseudo-calibrate with respect the following pair of random and planted
distributions which we denote $\nu$ and $\mu$ respectively.

See 1.1.2

Let the Hermite polynomials be
$h_{0}(x)=1,h_{1}(x)=x,h_{2}(x)=x^{2}-1,\ldots$. For
$a\in\mathbb{N}^{[n]^{k}}$ and variables $A_{e}$ for $e\in[n]^{k}$, define
$h_{a}(A):=\prod_{e\in[n]^{k}}h_{e}(A_{e})$. We will work with this Hermite
basis.

######  Lemma 5.2.

Let $I\in\mathbb{N}^{n},a\in\mathbb{N}^{[n]^{k}}$. For $i\in[n]$, let
$d_{i}=\sum_{i\in e\in[n]^{k}}a_{e}$. Let $c$ be the number of $i$ such that
$I_{i}+d_{i}$ is nonzero. Then, if $I_{i}+d_{i}$ are all even, we have

$\mathop{\mathbb{E}}_{\mu}[u^{I}h_{a}(A)]=\Delta^{c}\left(\frac{1}{\sqrt{\Delta
n}}\right)^{|I|}\prod_{e\in[n]^{k}}\left(\frac{\lambda}{(\Delta
n)^{\frac{k}{2}}}\right)^{a_{e}}$

Else, $\mathop{\mathbb{E}}_{\mu}[u^{I}h_{a}(v)]=0$.

###### Proof.

When $A\sim\mu$, for all $e\in[n]^{k}$, we have
$A_{e}=B_{e}+\lambda\prod_{i\leq k}u_{e_{i}}$. where
$B_{e}\sim\mathcal{N}(0,1)$.

Let’s analyze when the required expectation is nonzero. We can first condition
on $u$ and use the fact that for a fixed $t$,
$\mathop{\mathbb{E}}_{g\sim\mathcal{N}(0,1)}[h_{k}(g+t)]=t^{k}$ to obtain

$\mathop{\mathbb{E}}_{(u_{i},w_{e})\sim\mu}[u^{I}h_{a}(A)]=\mathop{\mathbb{E}}_{(u_{i})\sim\mu}[u^{I}\prod_{e\in[n]^{k}}(\lambda\prod_{i\leq
k}u_{e_{i}})^{a_{e}}]=\mathop{\mathbb{E}}_{(u_{i})\sim\mu}[\prod_{i\in[n]}u_{i}^{I_{i}+d_{i}}]\prod_{e\in[n]^{k}}\lambda^{a_{e}}$

Observe that this is nonzero precisely when all $I_{i}+d_{i}$ are even, in
which case

$\mathop{\mathbb{E}}_{(u_{i})\sim\mu}[\prod_{i\in[n]}u_{i}^{I_{i}+d_{i}}]=\Delta^{c}\left(\frac{1}{\sqrt{\Delta
n}}\right)^{\sum_{i\leq n}I_{i}+d_{i}}=\Delta^{c}\left(\frac{1}{\sqrt{\Delta
n}}\right)^{|I|}\prod_{e\in[n]^{k}}\left(\frac{1}{(\Delta
n)^{\frac{k}{2}}}\right)^{a_{e}}$

where we used the fact that $\sum_{e\in[n]^{k}}a_{e}=k\sum_{i\in[n]}d_{i}$.
This completes the proof.

Now, we can write the moment matrix in terms of graph matrices.

######  Definition 5.3.

Define the degree of SoS to be $D_{sos}=n^{C_{sos}\varepsilon}$ for some
constant $C_{sos}>0$ that we choose later.

######  Definition 5.4 (Truncation parameters).

Define the truncation parameters to be
$D_{V}=n^{C_{V}\varepsilon},D_{E}=n^{C_{E}\varepsilon}$ for some constants
$C_{V},C_{E}>0$.

######  Remark 5.5 (Choice of parameters).

We first set $\varepsilon$ to be a sufficiently small constant. Based on the
choice of $\varepsilon$, we will set the constant $C_{\Delta}>0$ sufficiently
small so that the planted distribution is well defined. Based on these
choices, we will set $C_{V},C_{E}$ to be sufficiently small constants to
satisfy all the inequalities we use in our proof. Based on these choices, we
can choose $C_{sos}$ to be sufficiently small to satisfy the inequalities we
use.

######  Remark 5.6.

The underlying graphs for the graph matrices have the following structure;
There will be $n$ vertices of a single type and the edges will be ordered
hyperedges of arity $k$.

######  Definition 5.7.

For the analysis of Tensor PCA, we will use the following notation.

  * -

For an index shape $U$ and a vertex $i$, define $deg^{U}(i)$ as follows: If
$i\in V(U)$, then it is the power of the unique index shape piece $A\in U$
such that $i\in V(A)$. Otherwise, it is $0$.

  * -

For an index shape $U$, define $deg(U)=\sum_{i\in V(U)}deg^{U}(i)$. This is
also the degree of the monomial that $U$ corresponds to.

  * -

For a shape $\alpha$ and vertex $i$ in $\alpha$, let
$deg^{\alpha}(i)=\sum_{i\in e\in E(\alpha)}l_{e}$.

  * -

For any shape $\alpha$, let $deg(\alpha)=deg(U_{\alpha})+deg(V_{\alpha})$.

We will now describe the decomposition of the moment matrix $\Lambda$.

######  Definition 5.8.

If a shape $\alpha$ satisfies the following properties:

  * -

$deg^{\alpha}(i)+deg^{U_{\alpha}}(i)+deg^{V_{\alpha}}(i)$ is even for all
$i\in V(\alpha)$,

  * -

$\alpha$ is proper,

  * -

$\alpha$ satisfies the truncation parameters $D_{sos},D_{V},D_{E}$.

then define

$\lambda_{\alpha}=\Delta^{|V(\alpha)|}\left(\frac{1}{\sqrt{\Delta
n}}\right)^{deg(\alpha)}\prod_{e\in E(\alpha)}\left(\frac{\lambda}{(\Delta
n)^{\frac{k}{2}}}\right)^{l_{e}}$

Otherwise, define $\lambda_{\alpha}=0$.

######  Corollary 5.9.

$\Lambda=\sum\lambda_{\alpha}M_{\alpha}$.

###  5.2 Proving positivity - Qualitative bounds

We use the canonical definition of $H_{\gamma}^{\prime}$ from Section 3.7.4.
In this section, we will prove the following qualitative bounds.

######  Lemma 5.10.

For all $U\in{\mathcal{I}}_{mid}$, $H_{Id_{U}}\succeq 0$

We define the following quantity to capture the contribution of the vertices
within $\tau$ to the Fourier coefficients.

######  Definition 5.11.

For $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, if
$deg^{\tau}(i)$ is even for all vertices $i\in V(\tau)\setminus
U_{\tau}\setminus V_{\tau}$, define

$S(\tau)=\Delta^{|V(\tau)|-|U_{\tau}|}\prod_{e\in
E(\tau)}\left(\frac{\lambda}{(\Delta n)^{\frac{k}{2}}}\right)^{l_{e}}$

Otherwise, define $S(\tau)=0$.

######  Lemma 5.12.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$,

$\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}\succeq 0$

We define the following quantity to capture the contribution of the vertices
within $\gamma$ to the Fourier coefficients.

######  Definition 5.13.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and
$\gamma\in\Gamma_{U,V}$, if $deg^{\gamma}(i)$ is even for all vertices $i$ in
$V(\gamma)\setminus U_{\gamma}\setminus V_{\gamma}$, define

$S(\gamma)=\Delta^{|V(\gamma)|-\frac{|U_{\gamma}|+|V_{\gamma}|}{2}}\prod_{e\in
E(\gamma)}\left(\frac{\lambda}{(\Delta n)^{\frac{k}{2}}}\right)^{l_{e}}$

Otherwise, define $S(\gamma)=0$.

######  Lemma 5.14.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}}H_{Id_{V}}^{-\gamma,\gamma}\preceq
H_{\gamma}^{\prime}$

####  5.2.1 Proof of Lemma 5.10

When we compose shapes $\sigma,\sigma^{\prime}$, from Definition 5.8, observe
that all vertices $i$ in $\lambda_{\sigma\circ\sigma^{\prime}}$ should have
$deg^{\sigma\circ\sigma^{\prime}}(i)+deg^{U_{\sigma\circ\sigma^{\prime}}}(i)+deg^{V_{\sigma\circ\sigma^{\prime}}}(i)$
to be even, in order for $\lambda_{\sigma\circ\sigma^{\prime}}$ to be nonzero.
To partially capture this notion conveniently, we will introduce the notion of
parity vectors.

######  Definition 5.15.

Define a parity vector $\rho$ to be a vector whose entries are in $\\{0,1\\}$.

######  Definition 5.16.

For $U\in{\mathcal{I}}_{mid}$, define ${\mathcal{P}}_{U}$ to be the set of
parity vectors $\rho$ whose coordinates are indexed by $U$.

######  Definition 5.17.

For a left shape $\sigma$, define
$\rho_{\sigma}\in{\mathcal{P}}_{V_{\sigma}}$, called the parity vector of
$\sigma$, to be the parity vector such that for each vertex $i\in V_{\sigma}$,
the $i$-th entry of $\rho_{\sigma}$ is the parity of
$deg^{U_{\sigma}}(i)+deg^{\sigma}(i)$, that is $(\rho_{\sigma})_{i}\equiv
deg^{U_{\sigma}}(i)+deg^{\sigma}(i)\pmod{2}$.

######  Definition 5.18.

For $U\in{\mathcal{I}}_{mid}$ and $\rho\in{\mathcal{P}}_{U}$, let
${\mathcal{L}}_{U,\rho}$ be the set of all left shapes
$\sigma\in{\mathcal{L}}_{U}$ such that $\rho_{\sigma}=\rho$, that is, the set
of all left shapes with parity vector $\rho$.

######  Definition 5.19.

For a shape $\tau$, for a $\tau$ coefficient matrix $H_{\tau}$ and parity
vectors
$\rho\in{\mathcal{P}}_{U_{\tau}},\rho^{\prime}\in{\mathcal{P}}_{V_{\tau}}$,
define the $\tau$-coefficient matrix $H_{\tau,\rho,\rho^{\prime}}$ as
$H_{\tau,\rho,\rho^{\prime}}(\sigma,\sigma^{\prime})=H_{\tau}(\sigma,\sigma^{\prime})$
if
$\sigma\in{\mathcal{L}}_{U_{\tau},\rho},\sigma^{\prime}\in{\mathcal{L}}_{V_{\tau},\rho^{\prime}}$
and $0$ otherwise.

######  Proposition 5.20.

For any shape $\tau$ and $\tau$-coefficient matrix $H_{\tau}$,
$H_{\tau}=\sum_{\rho\in{\mathcal{P}}_{U_{\tau}},\rho^{\prime}\in{\mathcal{P}}_{V_{\tau}}}H_{\tau,\rho,\rho^{\prime}}$

######  Proposition 5.21.

For any $U\in{\mathcal{I}}_{mid}$,
$H_{Id_{U}}=\sum_{\rho\in{\mathcal{P}}_{U}}H_{Id_{U},\rho,\rho}$

###### Proof.

For any $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}$, using Definition 5.8,
note that in order for $H_{Id_{U}}(\sigma,\sigma^{\prime})$ to be nonzero, we
must have $\rho_{\sigma}=\rho_{\sigma^{\prime}}$.

We define the following quantity to capture the contribution of the vertices
within $\sigma$ to the Fourier coefficients.

######  Definition 5.22.

For a shape $\sigma\in{\mathcal{L}}$, if $deg^{\sigma}(i)+deg^{U_{\sigma}}(i)$
is even for all vertices $i\in V(\sigma)\setminus V_{\sigma}$, define

$T(\sigma)=\Delta^{|V(\sigma)|-\frac{|V_{\sigma}|}{2}}\left(\frac{1}{\sqrt{\Delta
n}}\right)^{deg(U_{\sigma})}\prod_{e\in E(\sigma)}\left(\frac{\lambda}{(\Delta
n)^{\frac{k}{2}}}\right)^{l_{e}}$

Otherwise, define $T(\sigma)=0$.

######  Definition 5.23.

For $U\in{\mathcal{I}}_{mid}$ and $\rho\in{\mathcal{P}}_{U}$, define
$v_{\rho}$ to be the vector indexed by $\sigma\in{\mathcal{L}}$ such that
$v_{\rho}(\sigma)$ is $T(\sigma)$ if $\sigma\in{\mathcal{L}}_{U,\rho}$ and $0$
otherwise.

######  Proposition 5.24.

For all $U\in{\mathcal{I}}_{mid},\rho\in{\mathcal{P}}_{U}$,
$H_{Id_{U},\rho,\rho}=\frac{1}{|Aut(U)|}v_{\rho}v_{\rho}^{T}$.

###### Proof.

This follows by verifying the conditions of Definition 5.8.

See 5.10

###### Proof.

We have
$H_{Id_{U}}=\sum_{\rho\in{\mathcal{P}}_{U}}H_{Id_{U},\rho,\rho}=\frac{1}{|Aut(U)|}\sum_{\rho\in{\mathcal{P}}_{U}}v_{\rho}v_{\rho}^{T}\succeq
0$.

####  5.2.2 Proof of Lemma 5.12

The next proposition captures the fact that when we compose shapes
$\sigma,\tau,\sigma^{\prime T}$, in order for
$\lambda_{\sigma\circ\tau\sigma^{\prime T}}$ to be nonzero, the parities of
the degrees of the merged vertices should add up correspondingly.

######  Proposition 5.25.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, there exist
two sets of parity vectors $P_{\tau},Q_{\tau}\subseteq{\mathcal{P}}_{U}$ and a
bijection $\pi:P_{\tau}\rightarrow Q_{\tau}$ such that $H_{\tau}=\sum_{\rho\in
P_{\tau}}H_{\tau,\rho,\pi(\rho)}$.

###### Proof.

Using Definition 5.8, in order for $H_{\tau}(\sigma,\sigma^{\prime})$ to be
nonzero, in $\sigma\circ\tau\circ\sigma^{\prime}$, we must have that for all
$i\in U_{\tau}\cup V_{\tau}$,
$deg^{U_{\sigma}}(i)+deg^{U_{\sigma^{\prime}}}(i)+deg^{\sigma\circ\tau\circ\sigma^{\prime
T}}(i)$ must be even. In other words, for any $\rho\in{\mathcal{P}}_{U}$,
there is at most one $\rho^{\prime}\in{\mathcal{P}}_{U}$ such that if we take
$\sigma\in{\mathcal{L}}_{U,\rho},\sigma^{\prime}\in{\mathcal{L}}_{U}$ with
$H_{\tau}(\sigma,\sigma^{\prime})$ nonzero, then the parity of
$\sigma^{\prime}$ is $\rho^{\prime}$. Also, observe that $\rho^{\prime}$
determines $\rho$. We then take $P_{\tau}$ to be the set of $\rho$ such that
$\rho^{\prime}$ exists, $Q_{\tau}$ to be the set of $\rho^{\prime}$ and in
this case, we define $\pi(\rho)=\rho^{\prime}$.

We restate Definition 5.11 for convenience.

See 5.11

######  Proposition 5.26.

For any $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, suppose we
take $\rho\in P_{\tau}$. Let $\pi$ be the bijection from 5.25 so that
$\pi(\rho)\in Q_{\tau}$. Then,
$H_{\tau,\rho,\pi(\rho)}=\frac{1}{|Aut(U)|^{2}}S(\tau)v_{\rho}v_{\pi(\rho)}^{T}$.

###### Proof.

This follows by a straightforward verification of the conditions of Definition
5.8.

See 5.12

###### Proof.

Let $P_{\tau},Q_{\tau},\pi$ be from 5.25. For
$\rho,\rho^{\prime}\in{\mathcal{P}}_{U}$, let
$W_{\rho,\rho^{\prime}}=v_{\rho}(v_{\rho^{\prime}})^{T}$. Then,
$H_{Id_{U}}=\sum_{\rho\in{\mathcal{P}}_{U}}H_{Id_{U},\rho,\rho}=\frac{1}{|Aut(U)|}\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}$
and $H_{\tau}=\sum_{\rho\in
P_{\tau}}H_{\tau,\rho,\pi(\rho)}=\frac{1}{|Aut(U)|^{2}}S(\tau)\sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}$. We have

$\displaystyle\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}$
$\displaystyle=\frac{S(\tau)}{|Aut(U)|^{2}}\begin{bmatrix}\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}&\sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}\\\ \sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}^{T}&\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}\end{bmatrix}$

Since $\frac{S(\tau)}{|Aut(U)|^{2}}\geq 0$, it suffices to prove that
$\begin{bmatrix}\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}&\sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}\\\ \sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}^{T}&\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}\end{bmatrix}\succeq
0$. Consider

$\displaystyle\begin{bmatrix}\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}&\sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}\\\ \sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}^{T}&\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}\end{bmatrix}=$
$\displaystyle\begin{bmatrix}\sum_{\rho\in{\mathcal{P}}_{U}\setminus
P_{\tau}}W_{\rho,\rho}&0\\\ 0&\sum_{\rho\in{\mathcal{P}}_{U}\setminus
Q_{\tau}}W_{\rho,\rho}\end{bmatrix}$
$\displaystyle+\begin{bmatrix}\sum_{\rho\in
P_{\tau}}W_{\rho,\rho}&\sum_{\rho\in P_{\tau}}W_{\rho,\pi(\rho)}\\\
\sum_{\rho\in P_{\tau}}W_{\rho,\pi(\rho)}^{T}&\sum_{\rho\in
P_{\tau}}W_{\pi(\rho),\pi(\rho)}\end{bmatrix}$

We have $\sum_{\rho\in{\mathcal{P}}_{U}\setminus
P_{\tau}}W_{\rho,\rho}=\sum_{\rho\in{\mathcal{P}}_{U}\setminus
P_{\tau}}v_{\rho}v_{\rho}^{T}\succeq 0$. Similarly,
$\sum_{\rho\in{\mathcal{P}}_{U}\setminus Q_{\tau}}W_{\rho,\rho}\succeq 0$ and
so, the first term in the above expression,
$\begin{bmatrix}\sum_{\rho\in{\mathcal{P}}_{U}\setminus
P_{\tau}}W_{\rho,\rho}&0\\\ 0&\sum_{\rho\in{\mathcal{P}}_{U}\setminus
Q_{\tau}}W_{\rho,\rho}\end{bmatrix}$ is positive semidefinite. For the second
term,

$\displaystyle\begin{bmatrix}\sum_{\rho\in
P_{\tau}}W_{\rho,\rho}&\sum_{\rho\in P_{\tau}}W_{\rho,\pi(\rho)}\\\
\sum_{\rho\in P_{\tau}}W_{\rho,\pi(\rho)}^{T}&\sum_{\rho\in
P_{\tau}}W_{\pi(\rho),\pi(\rho)}\end{bmatrix}$ $\displaystyle=\sum_{\rho\in
P_{\tau}}\begin{bmatrix}W_{\rho,\rho}&W_{\rho,\pi(\rho)}\\\
W_{\rho,\pi(\rho)}^{T}&W_{\pi(\rho),\pi(\rho)}\end{bmatrix}$
$\displaystyle=\sum_{\rho\in
P_{\tau}}\begin{bmatrix}v_{\rho}v_{\rho}^{T}&v_{\rho}(v_{\pi(\rho)})^{T}\\\
v_{\pi(\rho)}(v_{\rho})^{T}&v_{\pi(\rho)}(v_{\pi(\rho)})^{T}\end{bmatrix}$
$\displaystyle=\sum_{\rho\in P_{\tau}}\begin{bmatrix}v_{\rho}\\\
v_{\pi(\rho)}\end{bmatrix}\begin{bmatrix}v_{\rho}&v_{\pi(\rho)}\end{bmatrix}$
$\displaystyle\succeq 0$

####  5.2.3 Proof of Lemma 5.14

The next proposition captures the fact that when we compose shapes
$\sigma,\gamma,\gamma^{T},\sigma^{\prime T}$, in order for
$\lambda_{\sigma\circ\gamma\circ\gamma^{\prime T}\circ\sigma^{\prime T}}$ to
be nonzero, the parities of the degrees of the merged vertices should add up
correspondingly.

######  Definition 5.27.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, for
$\gamma\in\Gamma_{U,V}$ and parity vectors
$\rho,\rho^{\prime}\in{\mathcal{P}}_{U}$, define the
$\gamma\circ\gamma^{T}$-coefficient matrix
$H_{Id_{V},\rho,\rho^{\prime}}^{-\gamma,\gamma}$ as
$H_{Id_{V},\rho,\rho^{\prime}}^{-\gamma,\gamma}(\sigma,\sigma^{\prime})=H_{Id_{V}}^{-\gamma,\gamma}(\sigma,\sigma^{\prime})$
if
$\sigma\in{\mathcal{L}}_{U,\rho},\sigma^{\prime}\in{\mathcal{L}}_{U,\rho^{\prime}}$
and $0$ otherwise.

######  Proposition 5.28.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, for all
$\gamma\in\Gamma_{U,V}$, there exists a set of parity vectors
$P_{\gamma}\subseteq{\mathcal{P}}_{U}$ such that

$H_{Id_{V}}^{-\gamma,\gamma}=\sum_{\rho\in
P_{\gamma}}H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}$

###### Proof.

Take any $\rho\in{\mathcal{P}}_{U}$. For
$\sigma\in{\mathcal{L}}_{U,\rho},\sigma^{\prime}\in{\mathcal{L}}_{U}$, since
$H_{Id_{V}}^{-\gamma,\gamma}(\sigma,\sigma^{\prime})=\frac{\lambda_{\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime
T}}}{|Aut(V)|}$, $H_{Id_{V}}^{-\gamma,\gamma}(\sigma,\sigma^{\prime})$ is
nonzero precisely when
$\lambda_{\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime T}}$ is nonzero.
For this quantity to be nonzero, using Definition 5.8, we get that it is
necessary, but not sufficient, that the parity vector of $\sigma^{\prime}$
must also be $\rho$. And also observe that there exists a set $P_{\gamma}$ of
parity vectors $\rho$ for which $H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}$ is
nonzero and their sum is precisely $H_{Id_{V}}^{-\gamma,\gamma}$.

######  Definition 5.29.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, for all
$\gamma\in\Gamma_{U,V}$ and parity vector $\rho\in{\mathcal{P}}_{U}$, define
the matrix $H^{\prime}_{\gamma,\rho,\rho}$ as
$H^{\prime}_{\gamma,\rho,\rho}(\sigma,\sigma^{\prime})=H^{\prime}_{\gamma}(\sigma,\sigma^{\prime})$
if $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U,\rho}$ and $0$ otherwise.

######  Proposition 5.30.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, for
$\gamma\in\Gamma_{U,V}$, $H_{\gamma}^{\prime}=\sum_{\rho\in
P_{\gamma}}H_{\gamma,\rho,\rho}^{\prime}$.

We restate Definition 5.13 for convenience.

See 5.13

######  Proposition 5.31.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, for all
$\gamma\in\Gamma_{U,V}$ and $\rho\in P_{\gamma}$,

$H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}=\frac{|Aut(U)|}{|Aut(V)|}S(\gamma)^{2}H^{\prime}_{\gamma,\rho,\rho}$

###### Proof.

Fix $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U,\rho}$ such that
$|V(\sigma\circ\gamma)|,|V(\sigma^{\prime}\circ\gamma)|\leq D_{V}$. Note that
$|V(\sigma)|-\frac{|V_{\sigma}|}{2}+|V(\sigma^{\prime})|-\frac{|V_{\sigma^{\prime}}|}{2}+2(|V(\gamma)|-\frac{|U_{\gamma}|+|V_{\gamma}|}{2})=|V(\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime
T})|$. Using Definition 5.8, we can easily verify that
$\lambda_{\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime
T}}=T(\sigma)T(\sigma^{\prime})S(\gamma)^{2}$. Therefore,
$H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}(\sigma,\sigma^{\prime})=\frac{|Aut(U)|}{|Aut(V)|}S(\gamma)^{2}H_{Id_{U},\rho,\rho}(\sigma,\sigma^{\prime})$.
Since
$H^{\prime}_{\gamma,\rho,\rho}(\sigma,\sigma^{\prime})=H_{Id_{U},\rho,\rho}(\sigma,\sigma^{\prime})$
whenever $|V(\sigma\circ\gamma)|,|V(\sigma^{\prime}\circ\gamma)|\leq D_{V}$,
this completes the proof.

See 5.14

###### Proof.

We have

$\displaystyle\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}}H_{Id_{V}}^{-\gamma,\gamma}$
$\displaystyle=\sum_{\rho\in
P_{\gamma}}\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}}H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}$
$\displaystyle=\sum_{\rho\in P_{\gamma}}H^{\prime}_{\gamma,\rho,\rho}$
$\displaystyle\preceq\sum_{\rho\in{\mathcal{P}}_{U}}H^{\prime}_{\gamma,\rho,\rho}$
$\displaystyle=H^{\prime}_{\gamma}$

where we used the fact that for all $\rho\in{\mathcal{P}}_{U}$, we have
$H^{\prime}_{\gamma,\rho,\rho}\succeq 0$ which can be proved the same way as
the proof of Lemma 5.10.

##  6 Qualitative bounds for Sparse PCA

###  6.1 Pseudo-calibration

######  Definition 6.1 (Slack parameter).

Define the slack parameter to be $\Delta=d^{-C_{\Delta}\varepsilon}$ for a
constant $C_{\Delta}>0$.

We will pseudo-calibrate with respect the following pair of random and planted
distributions which we denote $\nu$ and $\mu$ respectively.

See 1.1.2

We will again work with the Hermite basis of polynomials. For
$a\in\mathbb{N}^{m\times d}$ and variables $v_{i,j}$ for $i\in[m],j\in[n]$,
define $h_{a}(v):=\prod_{i\in[m],j\in[n]}h_{a_{i,j}}(v_{i,j})$.

######  Definition 6.2.

For a nonnegative integer $t$, define
$t!!=\begin{dcases}\frac{(2t)!}{t!2^{t}}=1\times 3\times\ldots\times
t,&\text{if t is odd}\\\ 0,&\text{otherwise}\end{dcases}$

######  Lemma 6.3.

Let $I\in\mathbb{N}^{d},a\in\mathbb{N}^{m\times d}$. For $i\in[m]$, let
$e_{i}=\sum_{j\in[d]}a_{ij}$ and for $j\in[d]$, let
$f_{j}=I_{j}+\sum_{i\in[m]}a_{ij}$. Let $c_{1}$ (resp. $c_{2}$) be the number
of $i$ (resp. $j$) such that $e_{i}>0$ (resp. $f_{j}>0$). Then, if
$e_{i},f_{j}$ are all even, we have

$\mathop{\mathbb{E}}_{\mu}[u^{I}h_{a}(v)]=\left(\frac{1}{\sqrt{k}}\right)^{|I|}\left(\frac{k}{d}\right)^{c_{2}}\Delta^{c_{1}}\prod_{i\in[m]}(e_{i}-1)!!\prod_{i,j}\frac{\sqrt{\lambda}^{a_{ij}}}{\sqrt{k}^{a_{ij}}}$

Else, $\mathop{\mathbb{E}}_{\mu}[u^{I}h_{a}(v)]=0$.

###### Proof.

$v_{1},\ldots,v_{m}\sim\mu$ can be written as
$v_{i}=g_{i}+\sqrt{\lambda}b_{i}l_{i}u$ where
$g_{i}\sim\mathcal{N}(0,I_{d}),l_{i}\sim\mathcal{N}(0,1),b_{i}\in\\{0,1\\}$
where $b_{i}=1$ with probability $\Delta$.

Let’s analyze when the required expectation is nonzero. We can first condition
on $b_{i},l_{i},u$ and use the fact that for a fixed $t$,
$\mathop{\mathbb{E}}_{g\sim\mathcal{N}(0,1)}[h_{k}(g+t)]=t^{k}$ to obtain

$\mathop{\mathbb{E}}_{(u,l_{i},b_{i},g_{i})\sim\mu}[u^{I}h_{a}(v)]=\mathop{\mathbb{E}}_{(u,l_{i},b_{i})\sim\mu}[u^{I}\prod_{i,j}(\sqrt{\lambda}b_{i}l_{i}u_{j})^{a_{ij}}]=\mathop{\mathbb{E}}_{(u,l_{i},b_{i})\sim\mu}[\prod_{i\in[m]}(b_{i}l_{i})^{e_{i}}\prod_{j\in[d]}u_{j}^{f_{j}}]\prod_{i,j}\sqrt{\lambda}^{a_{ij}}$

For this to be nonzero, the set of $c_{1}$ indices $i$ such that $e_{i}>0$,
should not have been resampled otherwise $b_{i}=0$, each of which happens
independently with probability $\Delta$. And the set of $c_{2}$ indices $j$
such that $f_{j}>0$ should have been such that $u_{j}$ is nonzero, each of
which happens independently with probability $\frac{k}{d}$. Since
$l_{i},u_{j}$ are have zero expectation in $\nu$, we need $e_{i},f_{j}$ to be
even. The expectation then becomes

$\Delta^{c_{1}}\left(\frac{k}{d}\right)^{c_{2}}\mathop{\mathbb{E}}_{(u,l_{i})\sim\mu}[\prod_{i\in[m]}l_{i}^{e_{i}}\prod_{j\in[d]}u_{j}^{f_{j}}]\prod_{i,j}\sqrt{\lambda}^{a_{ij}}=\left(\frac{1}{\sqrt{k}}\right)^{|I|}\left(\frac{k}{d}\right)^{c_{2}}\Delta^{c_{1}}\prod_{i\in[m]}(e_{i}-1)!!\prod_{i,j}\frac{\sqrt{\lambda}^{a_{ij}}}{\sqrt{k}^{a_{ij}}}$

The last equality follows because, for each $j$ such that $u_{j}$ is nonzero,
we have $u_{j}^{t}=(\frac{1}{\sqrt{k}})^{t}$ and
$\mathop{\mathbb{E}}_{g\sim\mathcal{N}(0,1)}[g^{t}]=(t-1)!!$ if $t$ is even.

Now, we can write the moment matrix in terms of graph matrices.

######  Definition 6.4.

Define the degree of SoS to be $D_{sos}=d^{C_{sos}\varepsilon}$ for some
constant $C_{sos}>0$ that we choose later.

######  Definition 6.5 (Truncation parameters).

Define the truncation parameters to be
$D_{V}=d^{C_{V}\varepsilon},D_{E}=d^{C_{E}\varepsilon}$ for some constants
$C_{V},C_{E}>0$.

######  Remark 6.6 (Choice of parameters).

We first set $\varepsilon>0$ to be a sufficiently small constant. Based on the
choice of $\varepsilon$, we will set the constant $C_{\Delta}>0$ sufficiently
small so that the planted distribution is well defined. Based on these
choices, we will set $C_{V},C_{E}$ to be sufficiently small constants to
satisfy all the inequalities we use in our proof. Based on these choices, we
can choose $C_{sos}$ to be sufficiently small to satisfy the inequalities we
use.

######  Remark 6.7.

The underlying graphs for the graph matrices have the following structure:
There will be two types of vertices - $d$ type $1$ vertices corresponding to
the dimensions of the space and $m$ type $2$ vertices corresponding to the
different input vectors. The shapes will correspond to bipartite graphs with
edges going between across of different types.

######  Definition 6.8.

For the analysis of Sparse PCA, we will use the following notation.

  * -

For a shape $\alpha$ and type $t\in\\{1,2\\}$, let $V_{t}(\alpha)$ denote the
vertices of $V(\alpha)$ that are of type $t$. Let
$|\alpha|_{t}=|V_{t}(\alpha)|$.

  * -

For an index shape $U$ and a vertex $i$, define $deg^{U}(i)$ as follows: If
$i\in V(U)$, then it is the power of the unique index shape piece $A\in U$
such that $i\in V(A)$. Otherwise, it is $0$.

  * -

For an index shape $U$, define $deg(U)=\sum_{i\in V(U)}deg^{U}(i)$. This is
also the degree of the monomial $p_{U}$.

  * -

For a shape $\alpha$ and vertex $i$ in $\alpha$, let
$deg^{\alpha}(i)=\sum_{i\in e\in E(\alpha)}l_{e}$.

  * -

For any shape $\alpha$, let $deg(\alpha)=deg(U_{\alpha})+deg(V_{\alpha})$.

  * -

For an index shape $U\in{\mathcal{I}}_{mid}$ and type $t\in\\{1,2\\}$, let
$U_{t}\in U$ denote the index shape piece of type $t$ in $U$ if it exists,
otherwise define $U_{t}$ to be $\emptyset$. Note that this is well defined
since for each type $t$, there is at most one index shape piece of type $t$ in
$U$ since $U\in{\mathcal{I}}_{mid}$. Also, denote by $|U|_{t}$ the length of
the tuple $U_{t}$.

We will now describe the decomposition of the moment matrix $\Lambda$.

######  Definition 6.9.

If a shape $\alpha$ satisfies the following properties:

  * -

Both $U_{\alpha}$ and $V_{\alpha}$ only contain index shape pieces of type
$1$,

  * -

$deg^{\alpha}(i)+deg^{U_{\alpha}}(i)+deg^{V_{\alpha}}(i)$ is even for all
$i\in V(\alpha)$,

  * -

$\alpha$ is proper,

  * -

$\alpha$ satisfies the truncation parameters $D_{sos},D_{V},D_{E}$.

then define

$\lambda_{\alpha}=\left(\frac{1}{\sqrt{k}}\right)^{deg(\alpha)}\left(\frac{k}{d}\right)^{|\alpha|_{1}}\Delta^{|\alpha|_{2}}\prod_{j\in
V_{2}(\alpha)}(deg^{\alpha}(j)-1)!!\prod_{e\in
E(\alpha)}\frac{\sqrt{\lambda}^{l_{e}}}{\sqrt{k}^{l_{e}}}$

Otherwise, define $\lambda_{\alpha}=0$.

######  Corollary 6.10.

$\Lambda=\sum\lambda_{\alpha}M_{\alpha}$.

###  6.2 Proving positivity - Qualitative bounds

We use the canonical definition of $H_{\gamma}^{\prime}$ from Section 3.7.4.
In this section, we will prove the following qualitative bounds.

######  Lemma 6.11.

For all $U\in{\mathcal{I}}_{mid}$, $H_{Id_{U}}\succeq 0$

For technical reasons, it will be convenient to discretize the Normal
distribution. The following fact follows from standard results on Gaussian
quadrature, see for e.g. [DKS17, Lemma 4.3].

######  Fact 6.12 (Discretizing the Normal distribution).

There is an absolute constant $C_{disc}$ such that, for any positive integer
$D$, there exists a distribution ${\mathcal{E}}$ over the real numbers
supported on $D$ points $p_{1},\ldots,p_{D}$, such that

  * -

$|p_{i}|\leq C_{disc}\sqrt{D}$ for all $i\leq D$ and

  * -

$\mathop{\mathbb{E}}_{g\sim{\mathcal{E}}}[g^{t}]=\mathop{\mathbb{E}}_{g\sim\mathcal{N}(0,1)}[g^{t}]$
for all $t=0,1,\ldots,2D-1$

We define the following quantity to capture the contribution of the vertices
within $\tau$ to the Fourier coefficients.

######  Definition 6.13.

For $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, if
$deg^{\tau}(i)$ is even for all vertices $i\in V(\tau)\setminus
U_{\tau}\setminus V_{\tau}$, define

$S(\tau)=\left(\frac{k}{d}\right)^{|\tau|_{1}-|U_{\tau}|_{1}}\Delta^{|\tau|_{2}-|U_{\tau}|_{2}}\prod_{j\in
V_{2}(\tau)\setminus U_{\tau}\setminus V_{\tau}}(deg^{\tau}(j)-1)!!\prod_{e\in
E(\tau)}\frac{\sqrt{\lambda}^{l_{e}}}{\sqrt{k}^{l_{e}}}$

Otherwise, define $S(\tau)=0$.

######  Definition 6.14.

For any shape $\tau$, suppose
$U^{\prime}=(U_{\tau})_{2},V^{\prime}=(V_{\tau})_{2}$ are the type $2$
vertices in $U_{\tau},V_{\tau}$ respectively. Define

$R(\tau)=(C_{disc}\sqrt{D_{E}})^{\sum_{j\in U^{\prime}\cup
V^{\prime}}deg^{\tau}(j)}$

where $C_{disc}$ is the constant from 6.12.

######  Lemma 6.15.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$,

$\begin{bmatrix}\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}\succeq 0$

We define the following quantity to capture the contribution of the vertices
within $\gamma$ to the Fourier coefficients.

######  Definition 6.16.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and
$\gamma\in\Gamma_{U,V}$, if $deg^{\gamma}(i)$ is even for all vertices $i$ in
$V(\gamma)\setminus U_{\gamma}\setminus V_{\gamma}$, define

$S(\gamma)=\left(\frac{k}{d}\right)^{|\gamma|_{1}-\frac{|U_{\gamma}|_{1}+|V_{\gamma}|_{1}}{2}}\Delta^{|\gamma|_{2}-\frac{|U_{\gamma}|_{2}+|V_{\gamma}|_{2}}{2}}\prod_{j\in
V_{2}(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}}(deg^{\gamma}(j)-1)!!\prod_{e\in
E(\gamma)}\frac{\sqrt{\lambda}^{l_{e}}}{\sqrt{k}^{l_{e}}}$

Otherwise, define $S(\gamma)=0$.

######  Lemma 6.17.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}R(\gamma)^{2}}H_{Id_{V}}^{-\gamma,\gamma}\preceq
H_{\gamma}^{\prime}$

####  6.2.1 Proof of Lemma 6.11

When we compose shapes $\sigma,\sigma^{\prime}$, from Definition 6.9, observe
that all vertices $i$ in $\lambda_{\sigma\circ\sigma^{\prime}}$ should have
$deg^{\sigma\circ\sigma^{\prime}}(i)+deg^{U_{\sigma\circ\sigma^{\prime}}}(i)+deg^{V_{\sigma\circ\sigma^{\prime}}}(i)$
to be even, in order for $\lambda_{\sigma\circ\sigma^{\prime}}$ to be nonzero.
To partially capture this notion conveniently, we will introduce the notion of
parity vectors.

######  Definition 6.18.

Define a parity vector $\rho$ to be a vector whose entries are in $\\{0,1\\}$.

######  Definition 6.19.

For $U\in{\mathcal{I}}_{mid}$, define ${\mathcal{P}}_{U}$ to be the set of
parity vectors $\rho$ whose coordinates are indexed by $U_{1}$ followed by
$U_{2}$.

######  Definition 6.20.

For a left shape $\sigma$, define
$\rho_{\sigma}\in{\mathcal{P}}_{V_{\sigma}}$, called the parity vector of
$\sigma$, to be the parity vector such that for each vertex $i\in V_{\sigma}$,
the $i$-th entry of $\rho_{\sigma}$ is the parity of
$deg^{U_{\sigma}}(i)+deg^{\sigma}(i)$, that is, $(\rho_{\sigma})_{i}\equiv
deg^{U_{\sigma}}(i)+deg^{\sigma}(i)\pmod{2}$.

######  Definition 6.21.

For $U\in{\mathcal{I}}_{mid}$ and $\rho\in{\mathcal{P}}_{U}$, let
${\mathcal{L}}_{U,\rho}$ be the set of all left shapes
$\sigma\in{\mathcal{L}}_{U}$ such that $\rho_{\sigma}=\rho$, that is, the set
of all left shapes with parity vector $\rho$.

######  Definition 6.22.

For a shape $\tau$, for a $\tau$ coefficient matrix $H_{\tau}$ and parity
vectors
$\rho\in{\mathcal{P}}_{U_{\tau}},\rho^{\prime}\in{\mathcal{P}}_{V_{\tau}}$,
define the $\tau$-coefficient matrix $H_{\tau,\rho,\rho^{\prime}}$ as
$H_{\tau,\rho,\rho^{\prime}}(\sigma,\sigma^{\prime})=H_{\tau}(\sigma,\sigma^{\prime})$
if
$\sigma\in{\mathcal{L}}_{U_{\tau},\rho},\sigma^{\prime}\in{\mathcal{L}}_{V_{\tau},\rho^{\prime}}$
and $0$ otherwise.

######  Proposition 6.23.

For any shape $\tau$ and $\tau$-coefficient matrix $H_{\tau}$,
$H_{\tau}=\sum_{\rho\in{\mathcal{P}}_{U_{\tau}},\rho^{\prime}\in{\mathcal{P}}_{V_{\tau}}}H_{\tau,\rho,\rho^{\prime}}$

######  Proposition 6.24.

For any $U\in{\mathcal{I}}_{mid}$,
$H_{Id_{U}}=\sum_{\rho\in{\mathcal{P}}_{U}}H_{Id_{U},\rho,\rho}$

###### Proof.

For any $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}$, using Definition 6.9,
note that in order for $H_{Id_{U}}(\sigma,\sigma^{\prime})$ to be nonzero, we
must have $\rho_{\sigma}=\rho_{\sigma^{\prime}}$.

We will now discretize the normal distribution while matching the first
$2D_{E}-1$ moments.

######  Definition 6.25.

Let ${\mathcal{D}}$ be a distribution over the real numbers obtained by
setting $D=D_{E}$ in 6.12. So, in particular, for any $x$ sampled from
${\mathcal{D}}$, we have $|x|\leq C_{disc}\sqrt{D_{E}}$ and for $t\leq
2D_{E}-1$, $\mathop{\mathbb{E}}_{x\sim{\mathcal{D}}}[x^{t}]=(t-1)!!$.

We define the following quantity to capture the contribution of the vertices
within $\sigma$ to the Fourier coefficients.

######  Definition 6.26.

For a shape $\sigma\in{\mathcal{L}}$, if $deg^{\sigma}(i)+deg^{U_{\sigma}}(i)$
is even for all vertices $i\in V(\sigma)\setminus V_{\sigma}$, define

$T(\sigma)=\left(\frac{1}{\sqrt{k}}\right)^{deg(U_{\sigma})}\left(\frac{k}{d}\right)^{|\sigma|_{1}-\frac{|V_{\sigma}|_{1}}{2}}\Delta^{|\sigma|_{2}-\frac{|V_{\sigma}|_{2}}{2}}\prod_{j\in
V_{2}(\sigma)\setminus V_{\sigma}}(deg^{\sigma}(j)-1)!!\prod_{e\in
E(\sigma)}\frac{\sqrt{\lambda}^{l_{e}}}{\sqrt{k}^{l_{e}}}$

Otherwise, define $T(\sigma)=0$.

######  Definition 6.27.

Let $U\in{\mathcal{I}}_{mid}$. Let $x_{i}$ for $i\in U_{2}$ be variables.
Denote them collectively as $x_{U_{2}}$. For $\rho\in{\mathcal{P}}_{U}$,
define $v_{\rho,x_{U_{2}}}$ to be the vector indexed by left shapes
$\sigma\in{\mathcal{L}}$ such that the $\sigma$th entry is
$T(\sigma)\prod_{i\in{U_{2}}}x_{i}^{deg^{\sigma}(i)}$ if
$\sigma\in{\mathcal{L}}_{U,\rho}$ and $0$ otherwise.

######  Proposition 6.28.

For any $U\in{\mathcal{I}}_{mid},\rho\in{\mathcal{P}}_{U}$, suppose $x_{i}$
for $i\in U_{2}$ are random variables sampled from ${\mathcal{D}}$. Then,

$H_{Id_{U},\rho,\rho}=\frac{1}{|Aut(U)|}\mathop{\mathbb{E}}_{x}[v_{\rho,x_{U_{2}}}v_{\rho,x_{U_{2}}}^{T}]$

###### Proof.

Observe that for $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U,\rho}$ and
$t\in\\{1,2\\}$,
$(|\sigma|_{t}-\frac{|V_{\sigma}|_{t}}{2})+(|\sigma^{\prime}|_{t}-\frac{|V_{\sigma^{\prime}}|_{t}}{2})=|\sigma\circ\sigma^{\prime}|_{t}$.
The result follows by verifying the conditions of Definition 6.9 and using
Definition 6.25.

See 6.11

###### Proof.

We have
$H_{Id_{U}}=\sum_{\rho\in{\mathcal{P}}_{U}}H_{Id_{U},\rho,\rho}=\frac{1}{|Aut(U)|}\sum_{\rho\in{\mathcal{P}}_{U}}\mathop{\mathbb{E}}_{x_{U_{2}}\sim{\mathcal{D}}^{U_{2}}}[v_{\rho,x_{U_{2}}}v_{\rho,x_{U_{2}}}^{T}]\succeq
0$.

####  6.2.2 Proof of Lemma 6.15

The next proposition captures the fact that when we compose shapes
$\sigma,\tau,\sigma^{\prime T}$, in order for
$\lambda_{\sigma\circ\tau\sigma^{\prime T}}$ to be nonzero, the parities of
the degrees of the merged vertices should add up correspondingly.

######  Proposition 6.29.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, there exist
two sets of parity vectors $P_{\tau},Q_{\tau}\subseteq{\mathcal{P}}_{U}$ and a
bijection $\pi:P_{\tau}\rightarrow Q_{\tau}$ such that $H_{\tau}=\sum_{\rho\in
P_{\tau}}H_{\tau,\rho,\pi(\rho)}$.

###### Proof.

Using Definition 6.9, in order for $H_{\tau}(\sigma,\sigma^{\prime})$ to be
nonzero, we must have that, in $\sigma\circ\tau\circ\sigma^{\prime}$, for all
$i\in U_{\tau}\cup V_{\tau}$,
$deg^{U_{\sigma}}(i)+deg^{U_{\sigma^{\prime}}}(i)+deg^{\sigma\circ\tau\circ\sigma^{\prime
T}}(i)$ must be even. In other words, for any $\rho\in{\mathcal{P}}_{U}$,
there is at most one $\rho^{\prime}\in{\mathcal{P}}_{U}$ such that if we take
$\sigma\in{\mathcal{L}}_{U,\rho},\sigma^{\prime}\in{\mathcal{L}}_{U}$ with
$H_{\tau}(\sigma,\sigma^{\prime})$ nonzero, then the parity of
$\sigma^{\prime}$ is $\rho^{\prime}$. Also, observe that $\rho^{\prime}$
determines $\rho$. We then take $P_{\tau}$ to be the set of $\rho$ such that
$\rho^{\prime}$ exists, $Q_{\tau}$ to be the set of $\rho^{\prime}$ and in
this case, we define $\pi(\rho)=\rho^{\prime}$.

We restate Definition 6.13 for convenience.

See 6.13

######  Proposition 6.30.

For any $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, suppose we
take $\rho\in P_{\tau}$. Let $\pi$ be the bijection from 6.29 so that
$\pi(\rho)\in Q_{\tau}$. Let
$U^{\prime}=(U_{\tau})_{2},V^{\prime}=(V_{\tau})_{2}$ be the type $2$ vertices
in $U_{\tau},V_{\tau}$ respectively. Let $x_{i}$ for $i\in U^{\prime}\cup
V^{\prime}$ be random variables independently sampled from ${\mathcal{D}}$.
Define $x_{U^{\prime}}$ (resp. $x_{V^{\prime}}$) to be the subset of variables
$x_{i}$ for $i\in U^{\prime}$ (resp. $i\in V^{\prime}$). Then,

$H_{\tau,\rho,\pi(\rho)}=\frac{1}{|Aut(U)|^{2}}S(\tau)\mathop{\mathbb{E}}_{x}\left[v_{\rho,x_{U^{\prime}}}\left(\prod_{i\in
U^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\tau}(i)}\right)v_{\pi(\rho),x_{V^{\prime}}}^{T}\right]$

###### Proof.

For $\sigma\in L_{U,\rho},\sigma^{\prime}\in{\mathcal{L}}_{U,\pi(\rho)}$ and
$t\in\\{1,2\\}$, we have
$(|\tau|_{t}-|U_{\tau}|_{t})+(|\sigma|_{t}-\frac{|V_{\sigma}|_{t}}{2})+(|\sigma^{\prime}|_{t}-\frac{|V_{\sigma^{\prime}}|_{t}}{2})=|\sigma\circ\tau\circ\sigma^{\prime}|_{t}$.
The result then follows by a straightforward verification of the conditions of
Definition 6.9 using Definition 6.25.

See 6.15

###### Proof.

Let $P_{\tau},Q_{\tau},\pi$ be from 6.29. Let