# A hierarchy of eigencomputations for polynomial optimization on the sphere

Nathaniel Johnston emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Benjamin Lovitz Aravindan Vijayaraghavan

(August 28, 2024)

###### Abstract

We introduce a convergent hierarchy of lower bounds on the minimum value of a
real homogeneous polynomial over the sphere. The main practical advantage of
our hierarchy over the sum-of-squares (SOS) hierarchy is that the lower bound
at each level of our hierarchy is obtained by a minimum eigenvalue
computation, as opposed to the full semidefinite program (SDP) required at
each level of SOS. In practice, this allows us to go to much higher levels
than are computationally feasible for the SOS hierarchy. For both hierarchies,
the underlying space at the $k$-th level is the set of homogeneous polynomials
of degree $2k$. We prove that our hierarchy converges as $O(1/k)$ in the level
$k$, matching the best-known convergence of the SOS hierarchy when the number
of variables $n$ is less than the half-degree $d$ (the best-known convergence
of SOS when $n\geq d$ is $O(1/k^{2})$). More generally, we introduce a
convergent hierarchy of minimum eigenvalue computations for minimizing the
inner product between a real tensor and an element of the spherical Segre-
Veronese variety, with similar convergence guarantees. As examples, we obtain
hierarchies for computing the (real) tensor spectral norm, and for minimizing
biquadratic forms over the sphere. Hierarchies of eigencomputations for more
general constrained polynomial optimization problems are discussed.

###### Contents

  1. 1 Introduction
    1. 1.1 The sum-of-squares hierarchy
    2. 1.2 Our polynomial optimization hierarchy
    3. 1.3 Our tensor optimization hierarchy
  2. 2 Background
  3. 3 Proof of convergence
  4. 4 Numerical implementation and examples
  5. 5 Tensor optimization hierarchy
    1. 5.1 Proof of convergence
    2. 5.2 Examples: Biquadratic forms and the real spectral norm of a tensor
  6. 6 Constrained polynomial optimization
  7. 7 Acknowledgments
  8. A Formula for $M_{k}(p)$

##  1 Introduction

We consider the fundamental task of minimizing a homogeneous degree-$D$
polynomial ${p(x)\in\real[x]_{D}}$ in $n$ variables $x=(x_{1},\dots,x_{n})$
over the unit sphere

$\displaystyle p_{\min}=\min_{x\in\mathcal{S}({}^{n})}p(x),$ (1)

where
$\mathcal{S}({}^{n})=\\{x\in{}^{n}:\lVert\mspace{1.0mu}x\mspace{1.0mu}\rVert=1\\}$
and $\lVert\mspace{1.0mu}\cdot\mspace{1.0mu}\rVert$ denotes the Euclidean
norm. Optimization problems of this form have applications in several areas
[FF21]. For example, for a special class of degree-three polynomials this
corresponds to computing the largest stable set of a graph [N+03, DK08]. As
another example, computing the $2\rightarrow 4$ norm (i.e.,
hypercontractivity) of a matrix $A$ is equivalent to maximizing the degree-
four polynomial $p(x)=\lVert\mspace{1.0mu}Ax\mspace{1.0mu}\rVert_{4}^{4}$ on
the unit sphere and has many connections to problems in computational
complexity, quantum information and designing matrices for compressive sensing
[BBH+12]. For $D=2$ this problem is equivalent to computing the minimum
eigenvalue of a symmetric matrix, which can be solved efficiently. However,
already for $D=3$ this problem is NP-hard as it contains the stable set
problem as a special case [N+03].

The sum-of-squares (SOS) hierarchy is a hierarchy of semidefinite programs
(SDPs) of increasing size whose optimum values approach $p_{\min}$ from below.
We propose a hierarchy of minimum eigenvalue computations that also approach
$p_{\min}$ from below. At the $k$-th level of both our hierarchy and the SOS
hierarchy, the underlying space is the set of homogeneous polynomials of
degree $2k$. However, our hierarchy has the advantage of merely requiring an
eigencomputation at each level, as opposed to the full SDP required at each
level of SOS.111We note that other works have also designed alternatives to
the SOS hierarchy that are based on spectral or eigenvector computation
[HSSS16, SS17]. However these algorithms are specialized for average-case
analysis (i.e., random instances) of tensor decompositions and finding planted
sparse vectors. In addition, we prove that the convergence of our hierarchy in
the level $k$ is similar to SOS: The difference between the lower bound
computed by our hierarchy and the true minimum $p_{\min}$ goes as $O(1/k)$ in
the level $k$. This is quadratically slower than the best-known convergence
$O(1/k^{2})$ of SOS when $D\leq 2n$, and matches the best-known convergence of
SOS when $D>2n$ [Rez95, DW12, FF21].222See also [BGG+17] which gives
multiplicative approximation guarantees for polynomial optimization over the
sphere using the sum of squares hierarchy. In particular, our convergence
result gives an alternate proof of the $O(1/k)$ convergence results of [Rez95,
DW12] for the SOS hierarchy. The main ingredient in our proof is the quantum
de Finetti theorem, which is a convergence result for a certain complex
optimization problem known as the quantum separability problem (see [DPS04,
Wat18]). We bypass the need to develop a specialized real quantum de Finetti
theorem (as was done in [DW12]) by proving that the real optimization problem
(1) is related to a certain complex optimization problem up to a constant
(Proposition 6). These results are presented in Section 3.

In Section 4 we describe an implementation of our hierarchy in MATLAB, and
present several examples to demonstrate its performance in comparison to the
SOS and Diagonally Dominant Sum-of-Squares (DSOS) hierarchies [AM19]. The
latter hierarchy optimizes over polynomials that admit a diagonally dominant
Gram matrix, which is stronger than being a sum-of-squares, in hopes of
computational savings.333In contrast to our hierarchy and the SOS hierarchy,
the DSOS hierarchy does not always converge [AM19, Proposition 3.15]. We find
that we can compute much higher levels of our hierarchy than either of these,
and can often outperform them in terms of time budget. For example, for the
Motzkin polynomial we can compute our hierarchy up to level $2000$, as opposed
to level $\sim 10$ for SOS or DSOS (Table 1). As another example, for random
homogeneous polynomials our hierarchy outperforms DSOS in numerical tests even
at a fixed level (Table 2). Here, both hierarchies are performing computations
in the space of homogeneous polynomials of degree $2k$, but our hierarchy is
using less computational resources and obtaining better bounds. Our hierarchy
can also compute non-trivial bounds for random dense polynomials in as many as
90 variables, which surpasses the 25 variables possible with SOS and 70
variables possible with DSOS (Table 3).

Let $S^{D}({}^{n})\subseteq({}^{n})^{\otimes D}$ be the symmetric subspace
(see Section 2). Under the standard isomorphism between $\real[x]_{D}$ and
$S^{D}({}^{n})$, one can view the optimization problem (1) as minimizing the
inner product between a symmetric tensor and a unit symmetric product tensor
(i.e. an element of the spherical Veronese variety). More generally, we
develop a hierarchy of eigencomputations for minimizing the inner product
between a real tensor and a unit partially-symmetric product tensor (i.e. an
element of the spherical Segre-Veronese variety). We prove that this more
general hierarchy also converges as $O(1/k)$. In particular, this gives
hierarchies for computing the real spectral norm of a real tensor, and for
minimizing a biquadratic form over the unit sphere. Computing the tensor
spectral norm is a well-studied problem with connections to planted clique,
tensor PCA and tensor decompositions [FK08, BV09, RM14]. These results are
presented in Section 5.

In Section 6 we consider minimizing a real homogeneous polynomial under more
general constraints. We develop a similar hierarchy of eigencomputations to
lower bound the constrained optimum, which converge to a certain analogous
complex constrained optimization problem. As mentioned above, in the case of
real polynomial optimization over the sphere (and more generally tensor
optimization over the spherical Segre-Veronese), we obtained our convergent
hierarchy by showing that this complex optimum is related to the real optimum
up to a constant (Proposition 6). It remains an interesting problem for future
work to determine how the complex optimum is related to the real optimum under
more general constraints.

In the remainder of this introduction, we describe the sum-of-squares
hierarchy for the polynomial optimization problem (1), introduce our hierarchy
for this problem, and describe the generalization of our hierarchy to tensor
optimization problems. For the sake of readability, we will defer some
definitions until Section 2.

###  1.1 The sum-of-squares hierarchy

Let us begin by considering the optimization problem (1). By [DW12, Lemma
B.2], we can (and will) assume $D$ is even.444If $D$ is odd, then
$\displaystyle\min_{x\in\mathcal{S}({}^{n})}p(x)=\frac{(D+1)^{(D+1)/2}}{D^{D/2}}\min_{(x,x_{n+1})\in\mathcal{S}({}^{n+1})}(x_{n+1}\cdot
p)(x,x_{n+1}),$ (2) where $(x_{n+1}\cdot p)(x,x_{n+1})$ is an (even) degree
$D+1$ homogeneous polynomial. We let $d=D/2$. The sum-of-squares (SOS)
hierarchy is a hierarchy of lower bounds on $p_{\min}$ which can be computed
by semidefinite programming (see e.g. [Par03, Section 3] and the references
therein for background on semidefinite programming). Let $\real[x]$ be the
real polynomial ring in $n$ variables $x=(x_{1},\dots,x_{n})$, let
$\real[x]_{k}$ be the set of homogeneous polynomials of degree $k$, let
$\Sigma_{n,k}\subseteq\real[x]_{2k}$ (or simply $\Sigma_{k}$ when $n$ is
understood) be the set of $n$-variate polynomials which are sums of squares of
homogeneous polynomials of degree $k$, let

$\displaystyle s(x)=\sum_{i=1}^{n}x_{i}^{2}\in\Sigma_{1}$ (3)

be the Euclidean norm squared, and let $s_{n,d}(x)=s(x)^{d}$ (see Section 2
for more details). For an integer $k\geq d$, the $k$-th level of the SOS
hierarchy computes the following SDP:

$\displaystyle\begin{split}\textup{maximize:}\quad&\ \gamma\\\ \textup{subject
to:}\quad&\ p(x)\cdot s(x)^{k-d}-\gamma\cdot s(x)^{k}\in\Sigma_{k}\end{split}$
(4)

This optimization can indeed be computed by semidefinite programming by
maximizing over $\gamma$ for which $p(x)\cdot s(x)^{k-d}-\gamma\cdot s(x)^{k}$
admits a positive semidefinite Gram matrix (see Section 2). To see
equivalences between the formulation (4) and other, perhaps more familiar
forms of the SOS hierarchy, see e.g. [dKLP05, Proposition 2] or [Lau19, Lemma
1.3]. Let $\gamma_{k}$ be the optimum value of this SDP. Then
$\gamma_{1}\leq\gamma_{2}\leq\dots$ and
$\lim_{k\rightarrow\infty}\gamma_{k}=p_{\min}$ [Rez95] (see also [DW12]).
Moreover, it is known that $p_{\min}-\gamma_{k}=O(1/k)$ [Rez95, DW12], which
can be improved to $O(1/k^{2})$ when $d\leq n$ [FF21].555In particular, our
analysis provides an alternate proof of the $O(1/k)$ convergence result of
[Rez95, DW12] for the SOS hierarchy.

The dual SDP to (4) is given as follows:

$\displaystyle\begin{split}\textup{minimize:}\quad&\
\tilde{\mathbb{E}}(p(x)\cdot s(x)^{k-d})\\\ \textup{subject to:}\quad&\
\tilde{\mathbb{E}}:\real[x]_{2k}\rightarrow\real\quad\text{linear}\\\ &\
\tilde{\mathbb{E}}\left(s(x)^{k}\right)=1\\\ &\ \tilde{\mathbb{E}}(q^{2})\geq
0\quad\text{for all}\quad q\in\real[x]_{k}.\end{split}$ (5)

The linear forms $\tilde{\mathbb{E}}$ are called pseudoexpectations. As both
the primal and dual problems are strictly feasible, there is no duality gap
and the optimum values of the SDPs (4) and (5) are equal.

###  1.2 Our polynomial optimization hierarchy

Like the SOS hierarchy, ours is a hierarchy of computations of increasing size
which converge to $p_{\min}$. The $k$-th level of both hierarchies perform
computations in the space $\real[x]_{2k}$. Our hierarchy has the computational
advantage of merely performing a minimum eigenvalue computation at each level,
as opposed to the full SDP required at each level of SOS. As a result, we can
compute hundreds (and in some cases, thousands) of levels of our hierarchy in
practice.

Let $S^{d}({}^{n})\subseteq({}^{n})^{\otimes d}$ be the symmetric subspace,
and let $M(p)\in\mathrm{Hom}(S^{d}({}^{n}))$ be the polynomial $p$ after the
sequence of maps

$\displaystyle\real[x]_{2d}\cong S^{2d}({}^{n})\subseteq S^{d}({}^{n})\otimes
S^{d}({}^{n})\cong\mathrm{Hom}(S^{d}({}^{n}))$ (6)

(see Section 2 for details). We often view $M(p)$ as a linear map on
$({}^{n})^{\otimes d}$ by setting it equal to zero on the orthogonal
complement to $S^{d}({}^{n})$. It is not difficult to check that $M(p)$ is a
Gram matrix for $p$, and we call it the canonical Gram matrix for $p$. In
Section 2 we prove that ${M(s_{n,d})\in\mathrm{Hom}(S^{d}({}^{n}))}$ is
positive definite.

At the $k$-th level, our hierarchy computes
$\nu_{k}:=\lambda_{\min}(M_{k}(p)M_{k}(s_{n,d})^{-1})$, where
$\lambda_{\min}(\cdot)$ denotes the minimum eigenvalue and

$\displaystyle
M_{k}(p):=\Pi_{n,k}(M(p)\otimes\mathds{1}_{n}^{\otimes{k-d}})\Pi_{n,k}.$ (7)

Here, $\Pi_{n,k}:({}^{n})^{\otimes k}\rightarrow({}^{n})^{\otimes k}$ is the
orthogonal projection onto the symmetric subspace $S^{k}({}^{n})$. An explicit
(and efficient) formula for the coordinates of $M_{k}(p)$ is derived in
Appendix A. We prove that $\nu_{1}\leq\nu_{2}\leq\dots$ and
$\lim_{k\rightarrow\infty}\nu_{k}=p_{\min}$. Moreover, we prove that
$p_{\min}-\nu_{k}=O(1/k)$.

Note that $\nu_{k}$ is equal to the optimum value of the SDP

$\displaystyle\begin{split}\textup{minimize:}\quad&\
\tilde{\Omega}(M_{k}(p)M_{k}(s_{n,d})^{-1})\\\ \textup{subject to:}\quad&\
\tilde{\Omega}:\mathrm{Hom}(S^{k}({}^{n}))\rightarrow\real\quad\text{linear}\\\
&\ \tilde{\Omega}(\mathds{1}_{n}^{\otimes k})=1\\\ &\
\tilde{\Omega}(qq^{\scriptscriptstyle\mathsf{T}})\geq 0\quad\text{for
all}\quad q\in S^{k}({}^{n}).\end{split}$ (8)

Indeed, the first, second and third conditions on $\tilde{\Omega}$ are
equivalent to i) $\Omega(M)=\operatorname{Tr}(\rho M)$ where
$\rho:S^{k}({}^{n})\rightarrow S^{k}({}^{n})$ is linear, ii)
$\operatorname{Tr}(\rho)=1$ and iii) $\rho$ is positive semidefinite. This
expression for $\nu_{k}$ reveals similarities between our hierarchy and the
SOS hierarchy: These conditions are analogous to the first, second, and third
conditions on the pseudoexpectation $\tilde{\mathbb{E}}$ in the SDP (5). Note
that $\nu_{k}=\max\\{\nu:M_{k}(p-\nu\cdot s(x)^{d})\succeq 0\\}$ where
$\succeq$ is the Loewner order; i.e. $\nu_{k}$ is the largest $\nu$ for which
the particular Gram matrix $M_{k}(p-\nu\cdot s(x)^{d})$ for the polynomial
$p(x)\cdot s(x)^{k-d}-\nu\cdot s(x)^{k}$ is positive semidefinite.666To see
this, note that  $\displaystyle\nu_{k}$
$\displaystyle=\lambda_{\min}(M_{k}(p)M_{k}(s_{n,d})^{-1})$ (9)
$\displaystyle=\lambda_{\min}(M_{k}(s_{n,d})^{-1/2}M_{k}(p)M_{k}(s_{n,d})^{-1/2})$
(10)
$\displaystyle=\max\\{\nu:M_{k}(s_{n,d})^{-1/2}M_{k}(p)M_{k}(s_{n,d})^{-1/2}-\nu\;\mathds{1}_{S^{k}({}^{n})}\succeq
0\\}$ (11) $\displaystyle=\max\\{\nu:M_{k}(p-\nu\cdot s(x)^{d})\succeq 0\\}.$
(12) This reveals that $\nu_{k}\leq\gamma_{k}$, i.e. the $k$-th level of our
hierarchy is weaker than the $k$-th level of the SOS hierarchy.

The dual SDP to (8) also has a satisfying comparison to the SOS SDP (4):

$\displaystyle\begin{split}\textup{maximize:}\quad&\ \nu\\\ \textup{subject
to:}\quad&\ M_{k}(p-\nu\cdot s_{n,d})\succeq 0.\end{split}$ (13)

For example, suppose we wish to determine whether $p_{\min}\geq 0$.777Both our
hierarchy and the SOS hierarchy can more generally be used to determine
whether an arbitrary polynomial (not necessarily homogeneous) is globally non-
negative: Given a polynomial $q(x)$ of degree $D$, let $p(x,y)=y^{D}\cdot
q(x_{1}/y,\dots,x_{n}/y)$ be its homogenization. Then $q$ is globally non-
negative if and only if $p_{\min}\geq 0$ [Mar08]. We would use the SOS
hierarchy to do this by checking whether $\gamma_{k}\geq 0$ at each level, or
equivalently whether there exists a positive semidefinite Gram matrix for
$p(x)\cdot s(x)^{k-d}$. In contrast, we would use our hierarchy to do this by
checking whether $\nu_{k}\geq 0$, or equivalently whether the single Gram
matrix $M_{k}(p)$ for $p(x)\cdot s(x)^{k-d}$ is positive semidefinite.
Surprisingly, our hierarchy still converges at a rate of $O(1/k)$. This is
quadratically slower than the best-known convergence $O(1/k^{2})$ of SOS when
$d\leq n$, and matches the best-known convergence of SOS when $d>n$ [Rez95,
DW12, FF21].

###  1.3 Our tensor optimization hierarchy

More generally, our techniques can be used to minimize the inner product
between a real tensor and an element of the spherical Segre-Veronese variety.
Let $p(x)\in\real[x]_{D}$ be a homogeneous degree-$D$ polynomial in $n$
variables. Note that

$\displaystyle\min_{x\in\mathcal{S}({}^{n})}p(x)=\min_{v\in\mathcal{S}({}^{n})}\langle\vec{p},v^{\otimes
D}\rangle,$ (14)

where $\vec{p}\in S^{D}({}^{n})$ is the polynomial $p$ after the isomorphism
$\real[x]_{D}\cong S^{D}({}^{n})$ (see Section 2). So minimizing $p(x)$ over
the unit sphere is equivalent to minimizing the inner product of the symmetric
tensor $\vec{p}$ with a unit symmetric product tensor $v^{\otimes D}$ (i.e. an
element of the (real) spherical Veronese variety). More generally, one can
choose positive integers $n_{1},\dots,n_{m}$ and $D_{1},\dots,D_{m}$, and a
tensor ${p}\in({}^{n_{1}})^{\otimes
D_{1}}\otimes\dots\otimes({}^{n_{m}})^{\otimes D_{m}}$, and consider the
minimization problem

$\displaystyle\min_{v_{j}\in\mathcal{S}({}^{n_{j}})}\langle p,v_{1}^{\otimes
D_{1}}\otimes\dots\otimes v_{m}^{\otimes D_{m}}\rangle.$ (15)

Tensors of the form $v_{1}^{\otimes D_{1}}\otimes\dots\otimes v_{m}^{\otimes
D_{m}}$ are by definition elements of the (real) Segre-Veronese variety. Our
hierarchy extends naturally to this setting, with similar convergence
guarantees. As was the case for real polynomial optimization, we can assume
that each $D_{j}=2d_{j}$ is even (see Proposition 11), and that $p\in
S^{2d_{1}}({}^{n_{1}})\otimes\dots\otimes S^{2d_{m}}({}^{n_{m}})$. For
$k\geq\max_{j}d_{j}$, the $k$-th level of our hierarchy computes the minimum
eigenvalue of the matrix $M_{k}(p)M_{k}(s_{n_{1},d_{1}}\otimes\dots\otimes
s_{n_{m},d_{m}})^{-1}$, where

$\displaystyle
M_{k}(p)=(\Pi_{n_{1},k}\otimes\dots\otimes\Pi_{n_{m},k})(M(p)\otimes\mathds{1}_{n_{1}}^{\otimes
k-d_{1}}\otimes\dots\otimes\mathds{1}_{n_{m}}^{\otimes
k-d_{m}})(\Pi_{n_{1},k}\otimes\dots\otimes\Pi_{n_{m},k}).$ (16)

Here, $\Pi_{n_{j},k}$ is the orthogonal projection onto $S^{k}({}^{n_{j}})$,
and $M(p)$ is $p$ viewed as an element of
$\mathrm{Hom}(S^{d_{1}}({}^{n_{1}})\otimes\dots\otimes
S^{d_{m}}({}^{n_{m}}))$. Just like our hierarchy for polynomial minimization,
we prove that this gives rise to a sequence of lower bounds on the true
minimum (15) converging as $O(1/k)$ in additive error. As applications, we use
this hierarchy to compute the tensor spectral norm and to minimize biquadratic
forms over the unit sphere.

##  2 Background

Let $\mathbb{F}$ be either  or $\mathbb{C}$, and let $n,d$ be positive
integers. Let $e_{1},\dots,e_{n}$ be the standard basis of $\mathbb{F}^{n}$.
Let $\mathbb{F}[x_{1},\dots,x_{n}]_{d}$ be the vector space of homogeneous
degree-$d$ polynomials in $n$ variables over $\mathbb{F}$. The permutation
group $S_{d}$ on $d$ letters acts on $(\mathbb{F}^{n})^{\otimes d}$ by
permuting factors, i.e. for $\sigma\in S_{d}$ we have

$\displaystyle\sigma\cdot(v_{1}\otimes\dots\otimes
v_{d})=v_{\sigma^{-1}(1)}\otimes\dots\otimes v_{\sigma^{-1}(d)}.$ (17)

Define the symmetric subspace
$S^{d}(\mathbb{F}^{n})\subseteq(\mathbb{F}^{n})^{\otimes d}$ to be the linear
subspace of tensors invariant under $S_{d}$. The symmetric subspace
$S^{d}(\mathbb{F}^{n})$ is isomorphic as an $\mathbb{F}$-vector space to
$\mathbb{F}[x_{1},\dots,x_{n}]_{d}$ via the map which sends $x_{i_{1}}\cdots
x_{i_{d}}$ to $\frac{1}{d!}f_{(i_{1},\dots,i_{d})},$ where

$\displaystyle f_{(i_{1},\dots,i_{d})}:=\sum_{\sigma\in
S_{d}}e_{i_{\sigma(1)}}\otimes\dots\otimes e_{i_{\sigma(d)}}.$ (18)

For a polynomial $p\in\mathbb{F}[x_{1},\dots,x_{n}]_{d}$ we let $\vec{p}\in
S^{d}(\mathbb{F}^{n})$ be the polynomial $p$ after this isomorphism.

For an $\mathbb{F}$-vector space $\mathcal{U}$, let
$\mathrm{Hom}_{\mathbb{F}}(\mathcal{U})$ denote the space of
$\mathbb{F}$-linear maps from $\mathcal{U}$ to $\mathcal{U}$. We will also
write $\mathrm{Hom}(\mathcal{U})$ when the field is clear from the context,
and identify $\mathrm{Hom}(\mathbb{F}^{n})$ with $n\times n$ matrices. For
positive integers $d\leq k$, let $[d]=\\{1,2,\dots,d\\}$ and $[d+1\cdot\cdot
k]=\\{d+1,d+2,\dots,k\\}$.

Let $\langle\cdot,\cdot\rangle$ be the standard bilinear form on
$\mathbb{F}^{n}$, extended to a bilinear form on $(\mathbb{F}^{n})^{\otimes
d}$ (and hence $S^{d}(\mathbb{F}^{n})$) by setting $\langle
u_{1}\otimes\dots\otimes u_{d},v_{1}\otimes\dots\otimes v_{d}\rangle=\langle
u_{1},v_{1}\rangle\cdots\langle u_{d},v_{d}\rangle$ and extending linearly.
For an -vector space $\mathcal{U}$ with a bilinear form
$\langle\cdot,\cdot\rangle$ we say that a map $M\in\mathrm{Hom}(\mathcal{U})$
is positive semidefinite ($M\succeq 0$) if $\langle u,Mu\rangle\geq 0$ for all
$u\in\mathcal{S}(\mathcal{U})$, and positive definite ($M\succ 0$) if $\langle
u,Mu\rangle>0$ for all $u\in\mathcal{S}(\mathcal{U})$. Let
$\langle\cdot|\cdot\rangle$ be the standard sesquilinear form on
$\mathbb{C}^{n}$, extended to a sesquilinear form on
$(\mathbb{C}^{n})^{\otimes d}$. For a $\mathbb{C}$-vector space $\mathcal{U}$
with a sesquilinear form $\langle\cdot|\cdot\rangle$ we say that a map
$M\in\mathrm{Hom}_{\mathbb{C}}(\mathcal{U})$ is positive semidefinite
($M\succeq 0$) if $\langle u|Mu\rangle\geq 0$ for all
$u\in\mathcal{S}(\mathcal{U})$, and positive definite ($M\succ 0$) if $\langle
u|Mu\rangle>0$ for all $u\in\mathcal{S}(\mathcal{U})$. For a vector
$v\in\mathbb{C}^{n}$, let $v^{*}$ be the conjugate-transpose of $v$. For a
matrix $M\in\mathrm{Hom}(\mathbb{F}^{n})$ and a real number
$p\in[1,\infty)\cup\\{\infty\\}$ we let
$\lVert\mspace{1.0mu}M\mspace{1.0mu}\rVert_{p}$ be the Schatten $p$-norm of
$M$ (see e.g. [Wat18]). We define the condition number of a positive definite
matrix $M$ to be $\kappa(M):=\lambda_{\max}(M)/\lambda_{\min}(M)$.

An orthonormal basis for $S^{d}(\mathbb{F}^{n})$ is given by

$\displaystyle\left\\{e_{(i_{1},\dots,i_{d})}:=f(i_{1},\dots,i_{d})f_{(i_{1},\dots,i_{d})}:1\leq
i_{1}\leq\dots\leq i_{d}\leq n\right\\},$ (19)

where

$\displaystyle f(i_{1},\dots,i_{d}):=(d!\cdot
r_{1}^{(i_{1},\dots,i_{d})}!\cdots r_{n}^{(i_{1},\dots,i_{d})}!)^{-1/2}$ (20)

and $r_{j}^{(i_{1},\dots,i_{d})}$ is the number of times $j$ appears in
$(i_{1},\dots,i_{d})$ (see Appendix A).

The transpose map $T\in\mathrm{Hom}(\mathrm{Hom}(\mathbb{F}^{n}))$ is the map
which sends a matrix $M$ to its transpose
$T(M)=M^{{\scriptscriptstyle\mathsf{T}}}$. The partial transpose map on the
first factor of $(\mathbb{F}^{n})^{\otimes d}$ is defined as
$T\otimes\mathds{1}_{\mathrm{Hom}((\mathbb{F}^{n})^{\otimes d-1})}$, where
$\mathds{1}_{\mathrm{Hom}((\mathbb{F}^{n})^{\otimes
d-1})}\in\mathrm{Hom}(\mathrm{Hom}((\mathbb{F}^{n})^{\otimes d-1}))$ is the
identity map. For a matrix $M\in\mathrm{Hom}((\mathbb{F}^{n})^{\otimes d}),$
we let

$\displaystyle
M^{\Gamma_{1}}:=(T\otimes\mathds{1}_{\mathrm{Hom}((\mathbb{F}^{n})^{\otimes
d-1})})(M)$ (21)

be the partial transpose of $M$ in the first factor. We define the partial
transpose map in the $j$-th factor for $j\in[d]$ similarly, and let
$M^{\Gamma_{j}}$ be the partial transpose of $M$ in the $j$-th factor. We
extend these definitions to linear maps on
$\mathbb{F}^{n_{1}}\otimes\dots\otimes\mathbb{F}^{n_{d}}$ for potentially
distinct $n_{1},\dots,n_{d}$ in the obvious way. See also [Wat18, Section
6.2.3].

The trace map $\operatorname{Tr}\in\mathrm{Hom}(\mathrm{Hom}(\mathbb{F}^{n}))$
is the map which sends a matrix $M$ to its trace. The partial trace map on the
first factor of $(\mathbb{F}^{n})^{\otimes d}$ is defined as
$\operatorname{Tr}\otimes\mathds{1}_{\mathrm{Hom}((\mathbb{F}^{n})^{\otimes
d-1})}$. For a matrix ${M\in\mathrm{Hom}((\mathbb{F}^{n})^{\otimes d})},$ we
let

$\displaystyle\operatorname{Tr}_{1}(M):=(\operatorname{Tr}\otimes\mathds{1}_{\mathrm{Hom}((\mathbb{F}^{n})^{\otimes
d-1})})(M)\in\mathrm{Hom}((\mathbb{F}^{n})^{\otimes{d-1}})$ (22)

be the partial trace of $M$ in the first factor. We define the partial trace
map on the $j$-th factor for $j\in[d]$ similarly, and let
$\operatorname{Tr}_{j}(M)$ be the partial trace of $M$ in the $j$-th factor.
For a subset $S\subseteq[d]$, we let
$\operatorname{Tr}_{S}(M)\in\mathrm{Hom}((\mathbb{F}^{n})^{\otimes{d-|S|}})$
be the composition of the partial traces of $M$ with respect to the factors
indexed by $S$. See also [DW12] or [Wat18]. We extend these definitions to
linear maps on $\mathbb{F}^{n_{1}}\otimes\dots\otimes\mathbb{F}^{n_{d}}$ for
potentially distinct $n_{1},\dots,n_{d}$ in the obvious way.

For a homogeneous polynomial $p\in\real[x_{1},\dots,x_{n}]_{2d}$, a Gram
matrix for $p$ is a matrix ${M\in\mathrm{Hom}(S^{d}({}^{n}))}$ for which
$p(x)=\langle x^{\otimes d},Mx^{\otimes d}\rangle$ for all $x\in{}^{n}$. We
say that $p$ is a sum of squares if there exist homogeneous polynomials
$q_{1},\dots,q_{\ell}\in\real[x_{1},\dots,x_{n}]_{d}$ for which
$p=q_{1}^{2}+\dots+q_{\ell}^{2}$. We denote the set of homogeneous polynomials
of degree $2d$ which are sums of squares by $\Sigma_{n,d}$, or simply
$\Sigma_{d}$ when the number of variables $n$ is clear from the context. It is
well-known that $p\in\Sigma_{d}$ if and only if there exists a positive semi-
definite Gram matrix for $p$ (see e.g. [Net16, Lemma 12]).

As mentioned in the introduction, we let $M(p)$ be the polynomial $p$ after
the sequence of maps

$\displaystyle\real[x]_{2d}\cong S^{2d}({}^{n})\subseteq S^{d}({}^{n})\otimes
S^{d}({}^{n})\cong\mathrm{Hom}(S^{d}({}^{n})).$ (23)

The first isomorphism is described above. The inclusion is clear: A
$(2d)$-factor tensor that is invariant under permutations of all $2d$ factors
is in particular invariant under permutations of the first $d$ factors and
permutations of the second $d$ factors (one could alternatively choose any
bipartition of the $2d$ factors into equally numbered parts). The last
isomorphism is standard and invokes the bilinear pairing to identity
$S^{d}({}^{n})$ with $S^{d}({}^{n})^{*}$ (here, $(\cdot)^{*}$ denotes the dual
vector space). It is easy to check that $M(p)$ forms a Gram matrix for $p$. We
will call $M(p)$ the canonical Gram matrix for $p$. Note that
$M(p)^{\scriptscriptstyle\mathsf{T}}=M(p)$ and $M(p)^{\Gamma_{j}}=M(p)$ for
all $j\in[d]$.

A recipe for obtaining $M(p)$ is also given in [Lau19, Section 1.1.3], and we
write down an explicit formula for the coordinates of $M(p)$ in Appendix A. We
often view $M(p)$ as a linear map on $({}^{n})^{\otimes d}$ by setting it
equal to zero on the orthogonal complement to $S^{d}({}^{n})$. For an integer
$k\geq d$ we define

$\displaystyle M_{k}(p):=\Pi_{n,k}(M(p)\otimes\mathds{1}_{n}^{\otimes
k-d})\Pi_{n,k}\in\mathrm{Hom}(S^{k}({}^{n})),$ (24)

where $\Pi_{n,k}$ is the orthogonal projection onto $S^{k}({}^{n})$. Note that
$M_{k}(p)$ is a Gram matrix for the polynomial $p(x)\cdot s(x)^{k-d}$, where
$s(x):=x_{1}^{2}+\dots+x_{n}^{2}$. Recall the definition
$s_{n,d}(x)=s(x)^{d}$.

We close this section by providing a few examples of $M(p)$, and proving that
$M(s_{n,d})$ is positive definite.

######  Example 1.

Let $p(x,y)=x^{2}+y^{2}+xy$. Then

$M(p)=\begin{bmatrix}1&1/2\\\ 1/2&1\end{bmatrix}\in\mathrm{Hom}({}^{2}).$

######  Example 2.

Let $p(x,y):=s(x,y)^{2}=(x^{2}+y^{2})^{2}$. Viewing $M(p)$ as a linear map on
$({}^{2})^{\otimes 2}$, we obtain

$\displaystyle M(p)=\begin{bmatrix}1&0&0&1/3\\\ 0&1/3&1/3&0\\\ 0&1/3&1/3&0\\\
1/3&0&0&1\end{bmatrix}\in\mathrm{Hom}(({}^{2})^{\otimes 2}).$ (25)

This can be verified by noting that $p(x,y)=\langle(x,y)^{\otimes
2},M(p)(x,y)^{\otimes 2}\rangle$, and if we reshape $M(p)$ into an element of
$({}^{2})^{\otimes 4}$ (a 16-dimensional vector), then it is invariant under
$S_{4}$. With respect to the orthonormal basis $e_{(1,1)},e_{(1,2)},e_{(2,2)}$
of $S^{2}({}^{2})$, $M(p)$ is given by

$\displaystyle M(p)=\begin{bmatrix}1&0&1/3\\\ 0&2/3&0\\\
1/3&0&1\end{bmatrix}\in\mathrm{Hom}(S^{2}({}^{2})).$ (26)

######  Example 3.

Let $p(x,y):=s(x,y)^{3}=(x^{2}+y^{2})^{3}$. With respect to the orthonormal
basis $e_{(1,1,1)},e_{(1,1,2)},e_{(1,2,2)},e_{(2,2,2)}$ of $S^{3}({}^{2})$,
$M(p)$ is given by

$\displaystyle M(p)=\begin{bmatrix}1&0&\sqrt{3}/5&0\\\ 0&3/5&0&\sqrt{3}/5\\\
\sqrt{3}/5&0&3/5&0\\\
0&\sqrt{3}/5&0&1\end{bmatrix}\in\mathrm{Hom}(S^{3}({}^{2})).$ (27)

This can be verified directly or using the formula derived in Appendix A.

######  Proposition 4.

Let $n,d$ be positive integers, and let
$s_{n,d}=(x_{1}^{2}+\dots+x_{n}^{2})^{d}\in\real[x_{1},\dots,x_{n}]_{2d}.$ It
holds that $M(s_{n,d})\succ 0$.

###### Proof.

We need to prove that $\langle v,M(s_{n,d})v\rangle>0$ for all
$v\in\mathcal{S}(S^{d}({}^{n}))$. This follows from

$\displaystyle\langle v,M(s_{n,d})v\rangle$
$\displaystyle=\langle\Pi_{n,2d}(v\otimes v),\vec{s}_{n,d}\rangle$ (28)
$\displaystyle=\langle\vec{q^{2}},\vec{s}_{n,d}\rangle$ (29)
$\displaystyle=\int_{x\in\mathcal{S}({}^{n})}q^{2}(x)d\mu(x)$ (30)
$\displaystyle>0,$ (31)

where $\mu$ is the normalized Lebesgue measure on $\mathcal{S}({}^{n})$ and
$q(x)\in\real[x]_{d}$ is the symmetric tensor $v$ after the isomorphism
$S^{d}({}^{n})\cong\real[x]_{d}$. The third line is [Rez95, Proposition 6.6].
This completes the proof. ∎

##  3 Proof of convergence

In this section we prove that our polynomial optimization hierarchy converges
as $O(1/k)$. We fix positive integers $n,d,$ and $k\geq d$, and a homogeneous
$n$-variate polynomial $p\in\real[x]_{2d}$. We also recall the definitions
$s_{n,d}=(x_{1}^{2}+\dots+x_{n}^{2})^{d}$,
$p_{\min}=\min_{x\in\mathcal{S}({}^{n})}p(x)$,
$M_{k}(p)=\Pi_{n,k}(M(p)\otimes\mathds{1}_{n}^{\otimes k-d})\Pi_{n,k}$ and
$\nu_{k}=\lambda_{\min}(M_{k}(p)M_{k}(s_{n,d})^{-1})$. Recall also the
condition number of a positive definite matrix $M$ is defined as
$\kappa(M)=\lambda_{\max}(M)/\lambda_{\min}(M)$. Note that $M_{k}(s_{n,d})$ is
invertible and moreover positive definite by Proposition 4. Furthermore, let

$\displaystyle
c_{d}=\sqrt{\frac{1}{2^{d}}\sum_{j=0}^{d}\frac{\binom{d}{j}^{2}}{\binom{2d}{2j}}}.$
(32)

######  Theorem 5.

For each natural number $k\geq d$, it holds that $\nu_{k}\leq p_{\min}$ and

$\displaystyle
p_{\min}-\nu_{k}\leq\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}\left(1+\kappa(M(s_{n,d}))\right)\frac{4d(n-1)}{c_{d}(k+1)}=O\left(\frac{1}{k}\right).$
(33)

In particular, $\lim_{k\rightarrow\infty}\nu_{k}=p_{\min}$.

Numerics suggest that

$\displaystyle\kappa(M(s_{n,d}))=\binom{n/2+d-1}{\lfloor d/2\rfloor},$ (34)

where the binomial function is extended to non-integer inputs via the Gamma
function. While the quantity
$\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}$ is perhaps unnatural
in the setting of polynomial optimization, it is equal to
$C_{n,d}\lVert\mspace{1.0mu}p\mspace{1.0mu}\rVert_{S(1)}$, where
$\lVert\mspace{1.0mu}p\mspace{1.0mu}\rVert_{S(1)}$ is the somewhat more
natural quantity $\max_{x\in\mathcal{S}({}^{n})}\lvert p(x)\rvert$, for some
constant $C_{n,d}$ which depends only on $n$ and $d$. This follows from the
equivalence of norms on finite-dimensional spaces and the fact that
$\lVert\mspace{1.0mu}\cdot\mspace{1.0mu}\rVert_{S(1)}$ defines a norm on
$\real[x]_{2d}$. Unsatisfying though this may be, it is not unprecedented: a
similar phenomenon occurs in the convergence results presented in [DW12] (and
clarified in [Lau19]) for the SOS hierarchy.

To prove Theorem 5 we require the following proposition, which relates
$p_{\min}$ to the optimum value of a certain complex optimization problem.

######  Proposition 6.

Let

$\displaystyle p_{\min}$ $\displaystyle:=\min_{x\in\mathcal{S}({}^{n})}p(x),$
(35) $\displaystyle p_{\min}^{\mathbb{C}}$
$\displaystyle:=\min_{v\in\mathcal{S}(\mathbb{C}^{n})}\operatorname{Tr}((vv^{*})^{\otimes
d}M(p)).$ (36)

Then

$\displaystyle p_{\min}^{\mathbb{C}}\leq
p_{\min}\leq\frac{p_{\min}^{\mathbb{C}}}{c_{d}}.$ (37)

This proposition will allow us to apply the quantum de Finetti theorem
(Theorem 7) directly in our analysis. Our $O(1/k)$ convergence result in
Theorem 5 in particular reproduces the known $O(1/k)$ convergence result for
the sum of squares hierarchy [DW12] (and also strengthens this to a
convergence result for our weaker hierarchy of eigencomputations).

###### Proof of Proposition 6.

Let $v\in\mathcal{S}(\mathbb{C}^{n})$ be such that
$p_{\min}^{\mathbb{C}}=\operatorname{Tr}((vv^{*})^{\otimes d}M(p))$. Let
$u=\mathrm{Re}({v})$ and $w=\mathrm{Im}({v})$. Recall that $M(p)$ is invariant
under partial transposition along any of the $d$ factors of $\mathbb{C}^{n}$.
In particular, $M(p)=\frac{1}{2}(M(p)+M(p)^{\Gamma_{1}})$, where
$(\cdot)^{\Gamma_{1}}=(T\otimes\mathds{1}_{\mathrm{Hom}({}^{n})}^{\otimes
d-1})(\cdot)$ denotes the partial transpose on the first factor (see Section
2). Thus,

$\displaystyle\operatorname{Tr}((vv^{*})^{\otimes d}M(p))$
$\displaystyle=\frac{1}{2}\operatorname{Tr}((vv^{*})^{\otimes
d}M(p))+\frac{1}{2}\operatorname{Tr}((vv^{*})^{\otimes d}M(p)^{\Gamma_{1}})$
(38) $\displaystyle=\frac{1}{2}\operatorname{Tr}((vv^{*})^{\otimes
d}M(p))+\frac{1}{2}\operatorname{Tr}((\overline{v}v^{\scriptscriptstyle\mathsf{T}})\otimes(vv^{*})^{\otimes
d-1}M(p))$ (39)
$\displaystyle=\operatorname{Tr}\bigg{(}(uu^{\scriptscriptstyle\mathsf{T}}+ww^{\scriptscriptstyle\mathsf{T}})\otimes(vv^{*})^{\otimes
d-1}M(p)\bigg{)}.$ (40)

Continuing in this way for the other factors, we obtain

$\displaystyle\operatorname{Tr}((vv^{*})^{\otimes d}M(p))$
$\displaystyle=\operatorname{Tr}\left((uu^{\scriptscriptstyle\mathsf{T}}+ww^{\scriptscriptstyle\mathsf{T}})^{\otimes
d}M(p)\right)$ (41) $\displaystyle=\langle\vec{p},(u\otimes u+w\otimes
w)^{\otimes d}\rangle$ (42) $\displaystyle=\langle\vec{p},\Pi_{n,2d}((u\otimes
u+w\otimes w)^{\otimes d})\rangle,$ (43)

where $\vec{p}$ is the polynomial $p$ after the isomorphism
$\real[x]_{2d}\cong S^{2d}({}^{n})$ (see Section 2), and $\Pi_{n,2d}$ is the
orthogonal projection onto $S^{2d}({}^{n})$. Let

$\displaystyle c=\lVert\mspace{1.0mu}\Pi_{n,2d}((u\otimes u+w\otimes
w)^{\otimes d})\mspace{1.0mu}\rVert.$ (44)

By [Rez13, Corollary 5.6] there exist real unit vectors
${v_{1}},\dots,{v_{d+1}}\in\mathcal{S}({}^{n})$ for which

$\displaystyle\frac{1}{c}\Pi_{n,2d}((u\otimes u+w\otimes w)^{\otimes
d})\in\mathrm{conv}\\{v_{1}^{\otimes 2d},\dots,v_{d+1}^{\otimes 2d}\\},$ (45)

where $\mathrm{conv}$ denotes the convex hull. Viewing these as elements of
$\mathrm{Hom}(S^{d}({}^{n}))$ and taking the trace of both sides, we obtain

$\displaystyle\frac{p_{\min}^{\mathbb{C}}}{c}\in\mathrm{conv}\\{\operatorname{Tr}(({v_{i}}{v_{i}}^{\scriptscriptstyle\mathsf{T}})^{\otimes
d}M(p)):i\in[d+1]\\}.$ (46)

Thus, there exists $i\in[d+1]$ for which
$\operatorname{Tr}(({v_{i}}{v_{i}}^{\scriptscriptstyle\mathsf{T}})^{\otimes
d}M(p))\leq\frac{p_{\min}^{\mathbb{C}}}{c}$.

To complete the proof, it suffices to show that $c\geq c_{d}$. Let
$U\in\mathrm{Hom}({}^{n})$ be an orthogonal matrix for which
$U(uu^{{\scriptscriptstyle\mathsf{T}}}+ww^{{\scriptscriptstyle\mathsf{T}}})U^{{\scriptscriptstyle\mathsf{T}}}=te_{1}e_{1}^{{\scriptscriptstyle\mathsf{T}}}+(1-t)e_{2}e_{2}^{{\scriptscriptstyle\mathsf{T}}}$
for some $t\in[0,1]$. Let $p(x,y)=(tx^{2}+(1-t)y^{2})^{d}\in\real[x,y]_{2d}$.
Note that

$\displaystyle\vec{p}$ $\displaystyle=\Pi_{n,2d}((te_{1}\otimes
e_{1}+(1-t)e_{2}\otimes e_{2})^{\otimes d})$ (47)
$\displaystyle=\frac{1}{(2d)!}\sum_{j=0}^{d}\binom{d}{j}t^{j}(1-t)^{d-j}f_{I_{j}}e_{I_{j}},$
(48)

where $I_{j}=(1^{(2j)},2^{(2(d-j))})$, and $i^{(j)}$ represents the number $i$
repeated $j$ times. It follows that

$\displaystyle c^{2}$
$\displaystyle=\lVert\mspace{1.0mu}\Pi_{n,2d}((te_{1}\otimes
e_{1}+(1-t)e_{2}\otimes e_{2})^{\otimes d})\mspace{1.0mu}\rVert^{2}$ (49)
$\displaystyle=\lVert\mspace{1.0mu}\vec{p}\mspace{1.0mu}\rVert^{2}$ (50)
$\displaystyle=\frac{1}{(2d)!}\sum_{j=0}^{d}\binom{d}{j}^{2}(2d)!(2j)!(2(d-j))!\;\;t^{j}(1-t)^{d-j}$
(51)
$\displaystyle=\sum_{j=0}^{d}\frac{\binom{d}{j}^{2}}{\binom{2d}{2j}}\;\;t^{j}(1-t)^{d-j}.$
(52)

To complete the proof, we will show that this quantity is minimized when
$t=1/2$. If we make the change of variables $x=t-1/2$ then we see that

$\displaystyle c^{2}$
$\displaystyle=\sum_{j=0}^{d}\frac{\binom{d}{j}^{2}}{\binom{2d}{2j}}\;\;\left(\frac{1}{2}+x\right)^{j}\left(\frac{1}{2}-x\right)^{d-j}$
(53)
$\displaystyle=\sum_{j=0}^{d}\frac{\binom{d}{j}^{2}}{\binom{2d}{2j}}\;\;\left(\sum_{k=0}^{j}\binom{j}{k}\frac{x^{k}}{2^{j-k}}\right)\left(\sum_{\ell=0}^{d-j}\binom{d-j}{\ell}\frac{(-x)^{\ell}}{2^{d-j-\ell}}\right)$
(54)
$\displaystyle=\sum_{j=0}^{d}\frac{\binom{d}{j}^{2}}{\binom{2d}{2j}}\;\;\sum_{k=0}^{j}\sum_{\ell=0}^{d-j}(-1)^{\ell}\binom{j}{k}\binom{d-j}{\ell}\frac{x^{k+\ell}}{2^{d-k-\ell}}.$
(55)

If we define $s=k+\ell$ then the above expression can be rewritten as

$\displaystyle c^{2}$
$\displaystyle=\frac{1}{2^{d}}\sum_{j,s=0}^{d}\frac{\binom{d}{j}^{2}}{\binom{2d}{2j}}(-2)^{s}\sum_{k=0}^{s}(-1)^{k}\binom{j}{k}\binom{d-j}{s-k}x^{s}.$
(56)

If $s$ is odd then the coefficient of $x^{s}$ above equals

$\displaystyle-2^{s-d}\sum_{j=0}^{d}\sum_{k=0}^{s}(-1)^{k}\frac{\binom{d}{j}^{2}\binom{j}{k}\binom{d-j}{s-k}}{\binom{2d}{2j}},$
(57)

which equals $0$ since replacing $j$ by $d-j$ and $k$ by $s-k$ in the term

$(-1)^{k}\frac{\binom{d}{j}^{2}\binom{j}{k}\binom{d-j}{s-k}}{\binom{2d}{2j}}$

results in another term with the same absolute value but its sign flipped. It
follows that $c^{2}$ is a sum of even powers of $x$, so it is minimized when
$x=0$ (i.e., when $t=1/2$), completing the proof. ∎

Our proof of convergence also relies on the quantum de Finetti theorem
[CKMR07]. We use the form of this theorem stated and proven in [Wat18, Theorem
7.26].

######  Theorem 7 (Quantum de Finetti theorem).

For any symmetric unit vector $v\in\mathcal{S}(S^{k}(\mathbb{C}^{n}))$, there
exists a matrix

$\displaystyle\tau\in\mathrm{conv}\\{(uu^{*})^{\otimes
d}:u\in\mathcal{S}(\mathbb{C}^{n})\\}\subseteq\mathrm{Hom}(S^{d}(\mathbb{C}^{n}))$
(58)

for which

$\displaystyle\lVert\mspace{1.0mu}\operatorname{Tr}_{[d+1\cdot\cdot
k]}(vv^{*})-\tau\mspace{1.0mu}\rVert_{1}\leq\frac{4d(n-1)}{k+1}.$ (59)

In the theorem statement, $\mathrm{conv}$ denotes the convex hull, and
$\operatorname{Tr}_{[d+1\cdot\cdot
k]}(vv^{*})\in\mathrm{Hom}((\mathbb{C}^{n})^{\otimes d-k})$ denotes the
partial trace of $vv^{*}$ over the subsystems $d+1,\dots,k$ (see Section 2).
Now we can prove Theorem 5.

###### Proof of Theorem 5.

Note that $\nu_{k}=\max\\{\nu:M_{k}(p-\nu\cdot s_{n,d})\succeq 0\\}$ (see
Footnote 6). For the inequality $\nu_{k}\leq p_{\min}$, note that since
$M_{k}(p(x)-\nu_{k}s_{n,d})\succeq 0$, we have

$\displaystyle p(x)-\nu_{k}$ $\displaystyle=\langle x^{\otimes
k},M_{k}(p(x)-\nu_{k}\;s_{n,d})x^{\otimes k}\rangle\geq 0$ (60)

for all $x\in\mathcal{S}({}^{n})$, so $p_{\min}-\nu_{k}\geq 0$.

For the bound, let $q_{k}(x)=p(x)-\nu_{k}\cdot s_{n,d}\in\real[x]_{2d},$ and
let $v\in\mathcal{S}(S^{k}({}^{n}))$ be a minimum (zero) eigenvector of
$M_{k}(q_{k}).$ By the quantum de Finetti theorem, there exists a matrix

$\displaystyle\tau\in\mathrm{conv}\\{(uu^{*})^{\otimes
d}:u\in\mathcal{S}(\mathbb{C}^{n})\\}\subseteq\mathrm{Hom}(S^{d}(\mathbb{C}^{n}))$
(61)

for which

$\displaystyle\lVert\mspace{1.0mu}\operatorname{Tr}_{[d+1\cdot\cdot
k]}(vv^{\scriptscriptstyle\mathsf{T}})-\tau\mspace{1.0mu}\rVert_{1}\leq\frac{4d(n-1)}{k+1}.$
(62)

Let

$\displaystyle q_{k,\min}$
$\displaystyle:=\min_{x\in\mathcal{S}({}^{n})}q_{k}(x)=p_{\min}-\nu_{k}$ (63)
$\displaystyle q_{k,\min}^{\mathbb{C}}$
$\displaystyle:=\min_{v\in\mathcal{S}(\mathbb{C}^{n})}\operatorname{Tr}((vv^{*})^{\otimes
d}M(q_{k})).$ (64)

Then

$\displaystyle q_{k,\min}^{\mathbb{C}}$
$\displaystyle\leq\operatorname{Tr}(M(q_{k})\tau)$ (65)
$\displaystyle=\operatorname{Tr}(M(q_{k})(\tau-\operatorname{Tr}_{[d+1\cdot\cdot
k]}(vv^{\scriptscriptstyle\mathsf{T}})))$ (66)
$\displaystyle\leq\lVert\mspace{1.0mu}M(q_{k})\mspace{1.0mu}\rVert_{\infty}\frac{4d(n-1)}{k+1}$
(67)
$\displaystyle\leq\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}\left(1+\kappa(M(s_{n,d}))\right)\frac{4d(n-1)}{k+1}$
(68)

The first line follows from convexity, the second line follows from the chain
of equalities

$\displaystyle\operatorname{Tr}(M(q_{k})\operatorname{Tr}_{[d+1\cdot\cdot
k]}(vv^{\scriptscriptstyle\mathsf{T}}))=\operatorname{Tr}((M(q_{k})\otimes\mathds{1}_{n}^{\otimes
k-d})vv^{\scriptscriptstyle\mathsf{T}})=\operatorname{Tr}(M_{k}(q_{k})vv^{\scriptscriptstyle\mathsf{T}})=0,$
(69)

the third line follows from the quantum de Finetti theorem and the matrix norm
inequality
$\operatorname{Tr}(AB)\leq\lVert\mspace{1.0mu}A\mspace{1.0mu}\rVert_{\infty}\lVert\mspace{1.0mu}B\mspace{1.0mu}\rVert_{1}$,
and the fourth line follows from

$\displaystyle\lVert\mspace{1.0mu}M(q_{k})\mspace{1.0mu}\rVert_{\infty}$
$\displaystyle\leq\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}+\lvert\nu_{k}\rvert\lVert\mspace{1.0mu}M(s_{n,d})\mspace{1.0mu}\rVert_{\infty}$
(70)
$\displaystyle\leq\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}\left(1+\frac{\lambda_{\max}(M(s_{n,d}))}{\lambda_{\min}(M(s_{n,d}))}\right)$
(71)

Here, the first line is the triangle inequality. The second line follows from
$\lVert\mspace{1.0mu}M(s_{n,d})\mspace{1.0mu}\rVert_{\infty}=\lambda_{\max}(M(s_{n,d}))$
by Proposition 4, and
$\lvert\nu_{k}\rvert\leq\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}\;\lambda_{\min}(M(s_{n,d}))^{-1}$
since choosing $\nu$ equal to minus the righthand side would guarantee
$M(p-\nu\;s_{n,d})\succeq 0$. It follows from Proposition 6 that

$\displaystyle p_{\min}-\nu_{k}$ $\displaystyle=q_{k,\min}$ (72)
$\displaystyle\leq\frac{q_{k,\min}^{\mathbb{C}}}{c_{d}}$ (73)
$\displaystyle=\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}\left(1+\kappa(M(s_{n,d}))\right)\frac{4d(n-1)}{c_{d}(k+1)}.$
(74)

This completes the proof. ∎

##  4 Numerical implementation and examples

While the quantity $\nu_{k}=\lambda_{\min}(M_{k}(p)M_{k}(s_{n,d})^{-1})$ that
defines the $k$-th level of our hierarchy is the minimum eigenvalue of a
matrix, it should not be computed as such, since doing so would require
computation of the inverse of the matrix $M_{k}(s_{n,d})$.888One could also
store $M_{k}(s_{n,d})^{-1}$ in a lookup table, or possibly write down an
explicit formula similar to Appendix A. We have chosen to rephrase the problem
as a generalized eigenvalue/eigenvector problem instead. An alternate way of
computing $\nu_{k}$ is to instead solve the generalized eigenvalue/eigenvector
problem

$\displaystyle M_{k}(p)\mathbf{v}=\lambda M_{k}(s_{n,d})\mathbf{v}.$ (75)

It is straightforward to show that the minimum generalized eigenvalue
$\lambda$ (i.e., the minimal $\lambda$ for which there is a vector
$\mathbf{v}$ solving Equation (75)) is equal to
$\nu_{k}=\lambda_{\min}(M_{k}(p)M_{k}(s_{n,d})^{-1})$. However, this
generalized eigenvalue can be found without inverting or multiplying any
matrices. Furthermore, there are extremely fast numerical algorithms for
solving this problem that can exploit the extreme sparsity of $M_{k}(p)$ and
$M_{k}(s_{n,d})$ [Ste02]; $M_{k}(s_{n,d})$ is sparse because $s_{n,d}$ itself
is sparse (i.e., most of its coefficients are equal to $0$), and $M_{k}(p)$ is
sparse when $k$ is large even if $p$ is dense (since

$\displaystyle
M_{k}(p)=\Pi_{n,k}(M(p)\otimes\mathds{1}_{n}^{\otimes{k-d}})\Pi_{n,k},$ (76)

and $\mathds{1}_{n}^{\otimes k-d}$ is sparse). These generalized eigenvalue
algorithms have been implemented in ARPACK [LSY98], making them available out-
of-the-box in SciPy, Mathematica, MATLAB, and many other popular computational
software packages. We have implemented the computation of $\nu_{k}$ in the
QETLAB package for MATLAB [Joh16].

######  Example 8 (Homogeneous Motzkin polynomial).

Let

$\displaystyle
p(x)=x_{1}^{2}x_{2}^{2}(x_{1}^{2}+x_{2}^{2}-3x_{3}^{2})+x_{3}^{6}$ (77)

be the homogeneous Motzkin polynomial [Lau09, Section 3.2] of degree $2d=6$.
This polynomial is non-negative but not a sum of squares; in fact, its minimum
value on the unit sphere is exactly $0$. Because this polynomial has so few
non-zero coefficients, the matrix $M_{k}(p)$ is extremely sparse, so our
hierarchy can be run at extremely high levels—on standard desktop hardware we
have been able to go up to level $k-d=2000$. Lower bounds on the minimum value
of this polynomial at various levels of the hierarchy, and the time required
to compute those bounds, are provided in Table 1.

| $k-d$ | lower bound | time
---|---|---
$0$ | $-0.500000$ |  $<0.01$ s
$1$ | $-0.200649$ |  $<0.01$ s
$2$ | $-0.127006$ |  $<0.01$ s
$3$ | $-0.084855$ |  $<0.01$ s
$4$ | $-0.053542$ |  $\hphantom{<}\ 0.01$ s
$5$ | $-0.045059$ |  $\hphantom{<}\ 0.02$ s
$10$ | $-0.018898$ |  $\hphantom{<}\ 0.06$ s
$15$ | $-0.011980$ |  $\hphantom{<}\ 0.12$ s
$20$ | $-0.008835$ |  $\hphantom{<}\ 0.21$ s
$25$ | $-0.007004$ |  $\hphantom{<}\ 0.33$ s
$30$ | $-0.005804$ |  $\hphantom{<}\ 0.77$ s
$50$ | $-0.003445$ |  $\hphantom{<}\ 1.85$ s
|  | $k-d$ | lower bound | time
---|---|---
$75$ | $-0.002285$ |  $4.96$ s
$100$ | $-0.001710$ |  $10.9$ s
$200$ | $-0.000852$ |  $1.27$ min
$300$ | $-0.000567$ |  $4.02$ min
$400$ | $-0.000425$ |  $10.4$ min
$500$ | $-0.000340$ |  $19.4$ min
$750$ | $-0.000227$ |  $1.36$ h
$1000$ | $-0.000170$ |  $3.99$ h
$1250$ | $-0.000136$ |  $5.86$ h
$1500$ | $-0.000113$ |  $10.5$ h
$1750$ | $-0.000097$ |  $19.2$ h
$2000$ | $-0.000085$ |  $30.4$ h
Table 1: Lower bounds on the minimum value of the Motzkin polynomial, as
computed by the $(k-d)$-th level of our hierarchy, as well as the time
required to compute those bounds.

Another lightweight alternative to the sum-of-squares hierarchy was introduced
in [AM19]. Their diagonally-dominant sum-of-squares (DSOS) hierarchy can
compute bounds on homogeneous polynomials via linear programming, which is
less memory-intensive than the semidefinite programs required by the sum-of-
squares hierarchy. However, our hierarchy based on (generalized) eigenvalues
is even less memory-intensive and can thus be used to bound polynomials of
even higher degree and even more variables. Furthermore, it seems to produce
better bounds on randomly-generated polynomials than the DSOS hierarchy does.

######  Example 9 (Random dense quartic polynomials).

Our hierarchy seems to perform quite well on randomly-generated polynomials.
To illustrate this fact, we generated a $10$-variable degree-$4$ homogeneous
polynomial with all $\binom{10+4-1}{4}=715$ coefficients independently drawn
from a standard normal distribution. Upper bounds on the maximum value of this
polynomial on the unit sphere, as computed by the SOS hierarchy, DSOS
hierarchy, and our hierarchy, are given in Table 2.999In both Table 2 and
Table 3, we use the timings reported in [AM19] for the DSOS and SOS
hierarchies, since their implementations of those hierarchies seem to be a bit
quicker than our implementations of them.

hierarchy | $k-d$ | upper bound | time
---|---|---|---
DSOS | $0$ | $5.9578$ |  $0.30$ s
| $1$ | $4.7756$ |  $0.92$ s
Ours | $0$ | $3.5674$ |  $0.16$ s
| $1$ | $2.6235$ |  $0.87$ s
| $2$ | $2.3612$ |  $5.94$ s
| $3$ | $2.2320$ |  $46.5$ s
| $4$ | $2.1547$ |  $5.03$ min
| $5$ | $2.1025$ |  $31.8$ min
| $6$ | $2.0650$ |  $3.48$ h
| $7$ | $2.0365$ |  $16.4$ h
SOS | $0$ | $1.8290$ |  $0.24$ s
Table 2: Upper bounds on the maximum value of a particular (randomly-
generated) dense $10$-variable quartic polynomial, and the times required to
compute these bounds by various hierarchies.

Of particular note is the fact the bound arising from the first (i.e.,
$k-d=0$) level of our hierarchy is better than the bound arising from the
first level of the DSOS hierarchy (or even the 2nd level of that hierarchy),
despite requiring fewer computational resources. We saw similar behaviour with
every randomly-generated example that we tried.

Our hierarchy is also less memory intensive; it was noted in [AM19] that while
the SOS hierarchy can only be used for quartic polynomials with up to $25$
variables or so, the DSOS hierarchy can be used for much larger quartic
polynomials with as many as $70$ variables. Our hierarchy can go even farther,
producing bounds on dense quartic polynomials with up to $90$ variables, as
detailed in Table 3.

| SOS | DSOS | Ours
---|---|---|---
$n$ | $k-d=0$ | $k-d=0$ | $k-d=1$ | $k-d=0$ | $k-d=1$ | $k-d=2$
$10$ |  $0.24$ s |  $0.30$ s |  $0.92$ s |  $0.16$ s |  $0.86$ s |  $6.61$ s
$15$ |  $5.60$ s |  $0.38$ s |  $6.26$ s |  $0.99$ s |  $8.80$ s |  $4.24$ min
$20$ |  $1.37$ min |  $0.74$ s |  $38.0$ s |  $4.42$ s |  $1.47$ min |  $1.90$ h
$25$ |  $17.8$ min |  $15.51$ s |  $6.15$ min |  $12.7$ s |  $10.5$ min |  $27.7$ h
$30$ | $\infty$ |  $7.88$ s | $\infty$ |  $31.6$ s |  $1.07$ h | $\infty$
$40$ | $\infty$ |  $10.7$ s | $\infty$ |  $2.56$ min |  $21.1$ h | $\infty$
$50$ | $\infty$ |  $26.0$ s | $\infty$ |  $9.39$ min | $\infty$ | $\infty$
$60$ | $\infty$ |  $58.1$ s | $\infty$ |  $31.2$ min | $\infty$ | $\infty$
$70$ | $\infty$ |  $5.71$ min | $\infty$ |  $1.55$ h | $\infty$ | $\infty$
$80$ | $\infty$ | $\infty$ | $\infty$ |  $4.56$ h | $\infty$ | $\infty$
$90$ | $\infty$ | $\infty$ | $\infty$ |  $11.4$ h | $\infty$ | $\infty$
Table 3: The time it takes for various levels of various hierarchies to
produce an upper bound on the maximum value of an $n$-variable quartic
polynomial. Values of $\infty$ indicate that memory limitations were exceeded,
so no bound could be computed on a standard desktop computer running MATLAB
with 16 GB of RAM.

##  5 Tensor optimization hierarchy

Let $n_{1},\dots,n_{m}$ and $D_{1},\dots,D_{m}$ be positive integers, and let
${p}\in({}^{n_{1}})^{\otimes D_{1}}\otimes\dots\otimes({}^{n_{m}})^{\otimes
D_{m}}$ be a tensor. In this section we generalize our hierarchy to solve the
following minimization problem:

$\displaystyle\min_{v_{j}\in\mathcal{S}({}^{n_{j}})}\langle p,v_{1}^{\otimes
D_{1}}\otimes\dots\otimes v_{m}^{\otimes D_{m}}\rangle.$ (78)

We let ${\bf n}=(n_{1},\dots,n_{m})$ and ${\bf D}=(D_{1},\dots,D_{m})$, and
denote this minimum value by $p^{({\bf n},{\bf D}/2)}_{\min}$ (soon we will
restrict without loss of generality to the case when $D_{1},\dots,D_{m}$ are
even, so dividing by $2$ in the index now will ease notation later).101010Note
that $p^{{\bf n},{\bf D}/2}_{\min}$ can also be computed using standard
polynomial optimization techniques (such as SOS) by setting
$\displaystyle\tilde{p}^{{\bf n},{\bf D}/2}(v_{1},\dots,v_{m})=\langle
p,v_{1}^{\otimes D_{1}}\otimes\dots\otimes v_{m}^{\otimes D_{m}}\rangle,$ (79)
which is a homogeneous degree-$(\sum_{i}D_{i})$ polynomial in the
$m(\sum_{i}n_{i})$ variables $v_{1},\dots,v_{m}$, and minimizing over
$\mathcal{S}({}^{n_{1}})\times\dots\times\mathcal{S}({}^{n_{m}})$. However it
is not obvious that $p^{{\bf n},{\bf D}/2}_{\min}$ can be computed by a
hierarchy of minimum eigenvalue computations, which is the main result of this
section.

######  Remark 10.

Note that if any of $D_{1},\dots,D_{m}$ are odd, then

$\displaystyle p_{\min}^{({\bf n},{\bf
D}/2)}=-\max_{v_{j}\in\mathcal{S}({}^{n_{j}})}\lvert\langle p,v_{1}^{\otimes
D_{1}}\otimes\dots\otimes v_{m}^{\otimes D_{m}}\rangle\rvert.$ (80)

However these quantities may differ if $D_{1},\dots,D_{m}$ are all even. For
example, if $p(x_{1},x_{2})=x_{1}^{2}$, then $p_{\min}=0$, but

$\displaystyle\max_{v\in\mathcal{S}({}^{2})}\lvert\langle\vec{p},v^{\otimes
2}\rangle\rvert=1.$ (81)

Note also that

$\displaystyle
p_{\min}^{(2,2),(1,1)/2}=\min_{u,v\in\mathcal{S}({}^{2})}\langle
e_{1}^{\otimes 2},u\otimes v\rangle=-1\neq p_{\min},$ (82)

so the minimum depends on the choice of ${\bf D}$.

We can assume $p\in S^{D_{1}}({}^{n_{1}})\otimes\dots\otimes
S^{D_{m}}({}^{n_{m}})$ without loss of generality by replacing
$p\rightarrow(\Pi_{n_{1},D_{1}}\otimes\dots\otimes\Pi_{n_{m},D_{m}})p$, where
$\Pi_{n_{j},D_{j}}$ is the orthogonal projection onto $S^{D_{j}}({}^{n_{j}})$.
The following proposition establishes that it suffices to assume
$D_{1},\dots,D_{m}$ are all even.

######  Proposition 11.

If $D_{1}$ is odd, then

$\displaystyle p_{\min}^{({\bf n},{\bf D}/2)}$
$\displaystyle=\frac{(D_{1}+1)^{(D_{1}+1)/2}}{D_{1}^{D_{1}/2}}(e_{n_{1}+1}\otimes
p)_{\min}^{(\tilde{{\bf n}},\tilde{{\bf D}}/2)}$ (83)
$\displaystyle=\frac{(D_{1}+1)^{(D_{1}+1)/2}}{D_{1}^{D_{1}/2}}\min_{\begin{subarray}{c}v_{j}\in\mathcal{S}({}^{n_{j}})\\\
1\neq
j\in[m]\end{subarray}}\;\;\;\min_{v_{1}\in\mathcal{S}({}^{n_{1}+1})}\langle
e_{n_{1}+1}\otimes p,v_{1}^{\otimes D_{1}+1}\otimes v_{2}^{\otimes
D_{2}}\otimes\dots\otimes v_{m}^{\otimes D_{m}}\rangle,$ (84)

where $\tilde{{\bf D}}=(D_{1}+1,D_{2},\dots,D_{m})$ and $\tilde{{\bf
n}}=(n_{1}+1,n_{2},\dots,n_{m})$, and we have embedded ${}^{n_{1}}$ into the
first $n_{1}$ coordinates of ${}^{n_{1}+1}$.

Note that $\tilde{D}_{1}=D_{1}+1$ is even and $\tilde{D}_{j}=D_{j}$ for all
$1\neq j\in[m]$. By symmetry, Proposition 11 implies analogous statements for
other $j\in[m]$. So one can assume $D_{1},\dots,D_{m}$ are all even, at the
expense of adding up to $m$ new variables.

###### Proof of Proposition 11.

For $v:=(v_{2},\dots,v_{m})$ fixed, define a polynomial
$p_{v}\in\real[x_{1},\dots,x_{n_{1}}]_{D_{1}}$ as

$\displaystyle p_{v}(v_{1})=\langle p,v_{1}^{\otimes D_{1}}\otimes\dots\otimes
v_{m}^{\otimes D_{m}}\rangle.$ (85)

By [DW12, Lemma B.2], we have

$\displaystyle p_{\min}^{({\bf n},{\bf D}/2)}$
$\displaystyle=\min_{\begin{subarray}{c}v_{j}\in\mathcal{S}({}^{n_{j}})\\\
1\neq
j\in[m]\end{subarray}}\;\;\;\min_{v_{1}\in\mathcal{S}({}^{n_{1}})}p_{v}(v_{1})$
(86)
$\displaystyle=\frac{(D_{1}+1)^{(D_{1}+1)/2}}{D_{1}^{D_{1}/2}}\min_{\begin{subarray}{c}v_{j}\in\mathcal{S}({}^{n_{j}})\\\
1\neq
j\in[m]\end{subarray}}\;\;\;\min_{v_{1}\in\mathcal{S}({}^{n_{1}+1})}(x_{n+1}\cdot
p_{v})(v_{1})$ (87)
$\displaystyle=\frac{(D_{1}+1)^{(D_{1}+1)/2}}{D_{1}^{D_{1}/2}}\min_{\begin{subarray}{c}v_{j}\in\mathcal{S}({}^{n_{j}})\\\
1\neq
j\in[m]\end{subarray}}\;\;\;\min_{v_{1}\in\mathcal{S}({}^{n_{1}+1})}\langle
e_{n_{1}+1}\otimes p,v_{1}^{\otimes D_{1}+1}\otimes v_{2}^{\otimes
D_{2}}\otimes\dots\otimes v_{m}^{\otimes D_{m}}\rangle.$ (88)

This completes the proof. ∎

In the remainder of this section, we assume $D_{1},\dots,D_{m}$ are even
without loss of generality. Let $d_{j}=D_{j}/2$ for all $j\in[m]$, and let
${\bf d}={\bf D}/2=(d_{1},\dots,d_{m})$. For positive integers $n,d$ let
$\vec{s}_{n,d}\in S^{2d}({}^{n})$ be the polynomial
$s_{n,d}=(x_{1}^{2}+\dots+x_{n}^{2})^{d}\in\real[x_{1},\dots,x_{n}]_{2d}$
after the isomorphism $\real[x_{1},\dots,x_{n}]_{2d}\cong S^{2d}({}^{n})$. For
a tensor $q\in S^{2d_{1}}({}^{n_{1}})\otimes\dots\otimes
S^{2d_{m}}({}^{n_{m}})$ and an integer $k\geq\max_{j}d_{j}$, let

$\displaystyle M_{k}^{({\bf n},{\bf
d})}(q):=(\Pi_{n_{1},k}\otimes\dots\otimes\Pi_{n_{m},k})(M(q)\otimes\mathds{1}_{n_{1}}^{\otimes
k-d_{1}}\otimes\dots\otimes\mathds{1}_{n_{m}}^{\otimes
k-d_{m}})(\Pi_{n_{1},k}\otimes\dots\otimes\Pi_{n_{m},k}),$ (89)

where $\Pi_{n_{j},k}$ is the orthogonal projection onto $S^{k}({}^{n_{j}})$,
and $M(q)$ is $q$ viewed as an element of
$\mathrm{Hom}(S^{d_{1}}({}^{n_{1}})\otimes\dots\otimes
S^{d_{m}}({}^{n_{m}}))$. The $k$-th level of our hierarchy computes

$\displaystyle\nu_{k}^{({\bf n},{\bf d})}:=\lambda_{\min}(M_{k}^{({\bf n},{\bf
d})}(p)\;M_{k}^{({\bf n},{\bf d})}(\vec{s}_{{\bf n},{\bf d}})^{-1}),$ (90)

where $\vec{s}_{{\bf n},{\bf
d}}:=\vec{s}_{n_{1},d_{1}}\otimes\dots\otimes\vec{s}_{n_{m},d_{m}}$. Note that

$\displaystyle M_{k}^{({\bf n},{\bf d})}(\vec{s}_{{\bf n},{\bf
d}})=M_{k}(s_{n_{1},d_{1}})\otimes\dots\otimes M_{k}(s_{n_{m},d_{m}})$ (91)

is positive definite (hence invertible) by Proposition 4. In Section 5.1 we
prove that the $\nu_{k}^{({\bf n},{\bf d})}$ converge to $p_{\min}^{({\bf
n},{\bf d})}$ from below at rate $O(1/k)$, and in Section 5.2 we use this
hierarchy to minimize biquadratic forms and compute the real spectral norm of
a tensor.

###  5.1 Proof of convergence

The following theorem proves that our hierarchy of minimum eigenvalue
computations $\nu_{k}^{({\bf n},{\bf d})}$ converges to $p_{\min}^{({\bf
n},{\bf d})}$ at a rate of $O(1/k)$. Let $c_{{\bf d}}=c_{d_{1}}\cdots
c_{d_{m}}$, where for a positive integer $d$ we define

$\displaystyle
c_{d}=\sqrt{\frac{1}{2^{d}}\sum_{j=0}^{d}\frac{\binom{d}{j}^{2}}{\binom{2d}{2j}}}.$
(92)

######  Theorem 12.

It holds that $\nu_{k}^{({\bf n},{\bf d})}\leq p_{\min}^{({\bf n},{\bf d})}$,
and

$\displaystyle p_{\min}^{({\bf n},{\bf d})}-\nu_{k}^{({\bf n},{\bf
d})}\leq\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}\left(1+\kappa(M(s_{{\bf
n},{\bf d}}))\right)\frac{4d(\max_{j}n_{j}-1)}{c_{{\bf
d}}(k+1)}=O\left(\frac{1}{k}\right),$ (93)

where $d=d_{1}+\dots+d_{m}$. In particular,
$\lim_{k\rightarrow\infty}\nu_{k}^{({\bf n},{\bf d})}=p_{\min}^{({\bf n},{\bf
d})}$.

Numerics indicate that

$\displaystyle\kappa(M(s_{{\bf n},{\bf d}}))=\binom{n_{1}/2+d_{1}-1}{\lfloor
d_{1}/2\rfloor}\cdots\binom{n_{m}/2+d_{m}-1}{\lfloor d_{m}/2\rfloor},$ (94)

where the binomial function is extended to non-integer inputs via the Gamma
function. We can make a similar remark as we did after Theorem 5: While the
quantity $\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}$ is perhaps
unnatural, it is equal to $C_{({\bf n},{\bf
d})}\lVert\mspace{1.0mu}p\mspace{1.0mu}\rVert_{S_{({\bf n},{\bf d})}(1)}$,
where $\lVert\mspace{1.0mu}p\mspace{1.0mu}\rVert_{S_{({\bf n},{\bf d})}(1)}$
is the somewhat more natural quantity

$\displaystyle\max_{v_{j}\in\mathcal{S}({}^{n_{j}})}\lvert\langle
p,v_{1}^{\otimes 2d_{1}}\otimes\dots\otimes v_{m}^{\otimes
2d_{m}}\rangle\rvert,$ (95)

for some constant $C_{({\bf n},{\bf d})}$ which depends only on ${\bf n}$ and
${\bf d}$. This follows from the equivalence of norms on finite-dimensional
spaces and the fact that
$\lVert\mspace{1.0mu}\cdot\mspace{1.0mu}\rVert_{S_{({\bf n},{\bf d})}(1)}$
defines a norm on $S^{2d_{1}}({}^{n_{1}})\otimes\dots\otimes
S^{2d_{m}}({}^{n_{m}})$. Alternatively, one can use the bound
$\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}\leq\lVert\mspace{1.0mu}p\mspace{1.0mu}\rVert_{2}$.

To prove the theorem we require the following proposition. In the proposition
we view $M(p)$ as an element of
$\mathrm{Hom}_{\mathbb{C}}(S^{d_{1}}(\mathbb{C}^{n_{1}})\otimes\dots\otimes
S^{d_{m}}(\mathbb{C}^{n_{m}}))$ under the standard inclusion
$\real\subseteq\mathbb{C}$, and recall that $v^{*}$ denotes the conjugate-
transpose of $v$.

######  Proposition 13.

Let $p_{\min}=p_{\min}^{({\bf n},{\bf d})}$ and

$\displaystyle p_{\min}^{\mathbb{C}}$
$\displaystyle=\min_{v_{j}\in\mathcal{S}(\mathbb{C}^{n_{j}})}\operatorname{Tr}((v_{1}v_{1}^{*})^{\otimes
d_{1}}\otimes\dots\otimes(v_{m}v_{m}^{*})^{\otimes d_{m}}M(p)).$ (96)

It holds that

$\displaystyle p_{\min}^{\mathbb{C}}\leq
p_{\min}\leq\frac{p_{\min}^{\mathbb{C}}}{c_{{\bf d}}}.$ (97)

###### Proof.

It will be convenient to view $M(p)$ as a map on $(\mathbb{C}^{n})^{\otimes
d}$ by setting it equal to zero on the orthogonal complement to
$S^{d}(\mathbb{C}^{n})$. Let
$v_{1}\in\mathcal{S}(\mathbb{C}^{n_{1}}),\dots,v_{m}\in\mathcal{S}(\mathbb{C}^{n_{m}})$
be such that

$\displaystyle
p_{\min}^{\mathbb{C}}=\operatorname{Tr}((v_{1}v_{1}^{*})^{\otimes
d_{1}}\otimes\dots\otimes(v_{m}v_{m}^{*})^{\otimes d_{m}}M(p)).$ (98)

Let $u_{j}=\mathrm{Re}({v_{j}})$ and $w_{j}=\mathrm{Im}({v_{j}})$ for each
$j\in[m]$. Note that $M(p)$ is invariant under partial transposition along any
of the $d_{1}$ factors of $\mathbb{C}^{n_{1}}$. In particular,
$M(p)=\frac{1}{2}(M(p)+M(p)^{\Gamma_{1}})$, where $(\cdot)^{\Gamma_{1}}$
denotes the partial transpose on the first factor of $\mathbb{C}^{n_{1}}$.
Thus,

$\displaystyle\operatorname{Tr}((v_{1}v_{1}^{*})^{\otimes
d_{1}}\otimes\dots\otimes(v_{m}v_{m}^{*})^{\otimes d_{m}}M(p))$ (99)
$\displaystyle=\frac{1}{2}\operatorname{Tr}((v_{1}v_{1}^{*})^{\otimes
d_{1}}\otimes\dots\otimes(v_{m}v_{m}^{*})^{\otimes
d_{m}}M(p))+\frac{1}{2}\operatorname{Tr}((v_{1}v_{1}^{*})^{\otimes
d_{1}}\otimes\dots\otimes(v_{m}v_{m}^{*})^{\otimes d_{m}}M(p)^{\Gamma_{1}})$
(100) $\displaystyle=\frac{1}{2}\operatorname{Tr}((v_{1}v_{1}^{*})^{\otimes
d_{1}}\otimes\dots\otimes(v_{m}v_{m}^{*})^{\otimes
d_{m}}M(p))+\frac{1}{2}\operatorname{Tr}((\overline{v}_{1}v_{1}^{\scriptscriptstyle\mathsf{T}})\otimes(v_{1}v_{1}^{*})^{\otimes
d_{1}-1}\otimes\dots\otimes(v_{m}v_{m}^{*})^{\otimes d_{m}}M(p))$ (101)
$\displaystyle=\operatorname{Tr}\bigg{(}(u_{1}u_{1}^{\scriptscriptstyle\mathsf{T}}+w_{1}w_{1}^{\scriptscriptstyle\mathsf{T}})\otimes(v_{1}v_{1}^{*})^{\otimes
d_{1}-1}\otimes\dots\otimes(v_{m}v_{m}^{*})^{\otimes d_{m}}M(p)\bigg{)}.$
(102)

Continuing in this way for the other factors, we obtain

$\displaystyle\operatorname{Tr}((v_{1}v_{1}^{*})$ ${}^{\otimes
d_{1}}\otimes\dots\otimes(v_{m}v_{m}^{*})^{\otimes d_{m}}M(p))$ (103)
$\displaystyle=\operatorname{Tr}((u_{1}u_{1}^{\scriptscriptstyle\mathsf{T}}+w_{1}w_{1}^{\scriptscriptstyle\mathsf{T}})^{\otimes
d_{1}}\otimes\dots\otimes(u_{m}u_{m}^{\scriptscriptstyle\mathsf{T}}+w_{m}w_{m}^{\scriptscriptstyle\mathsf{T}})^{\otimes
d_{m}}M(p))$ (104) $\displaystyle=\langle p,(u_{1}\otimes u_{1}+w_{1}\otimes
w_{1})^{\otimes d_{1}}\otimes\dots\otimes(u_{m}\otimes u_{m}+w_{m}\otimes
w_{m})^{\otimes d_{m}}\rangle$ (105) $\displaystyle=\langle
p,\Pi_{n_{1},2d_{1}}((u_{1}\otimes u_{1}+w_{1}\otimes w_{1})^{\otimes
d_{1}})\otimes\dots\otimes\Pi_{n_{m},2d_{m}}((u_{m}\otimes u_{m}+w_{m}\otimes
w_{m})^{\otimes d_{m}})\rangle,$ (106)

where $\Pi_{n_{j},2d_{j}}$ is the orthogonal projection onto
$S^{2d_{j}}({}^{n_{j}})$. For each $j\in[m]$, let

$\displaystyle c^{(j)}=\lVert\mspace{1.0mu}\Pi_{n_{j},2d_{j}}((u_{j}\otimes
u_{j}+w_{j}\otimes w_{j})^{\otimes d_{j}})\mspace{1.0mu}\rVert$ (107)

By [Rez13, Corollary 5.6] for each $j\in[m]$ there exist real unit vectors
${z_{j,1}},\dots,{z_{j,d_{j}+1}}\in\mathcal{S}({}^{n_{j}})$ for which

$\displaystyle\frac{1}{c^{(j)}}\Pi_{n_{j},2d_{j}}((u_{j}\otimes
u_{j}+w_{j}\otimes w_{j})^{\otimes d_{j}})\in\mathrm{conv}\\{z_{j,1}^{\otimes
2d_{j}},\dots,z_{j,d_{j}+1}^{\otimes 2d_{j}}\\}.$ (108)

Thus,

$\displaystyle\frac{p_{\min}^{\mathbb{C}}}{c^{(1)}\cdots
c^{(m)}}\in\mathrm{conv}\\{\operatorname{Tr}((z_{1,i_{1}}z_{1,i_{1}}^{\scriptscriptstyle\mathsf{T}})^{\otimes
d_{1}}\otimes\dots\otimes(z_{m,i_{m}}z_{m,i_{m}}^{\scriptscriptstyle\mathsf{T}})^{\otimes
d_{m}}M(p)):i_{j}\in[d_{j}+1]\\}.$ (109)

Thus, there exist $i_{1}\in[d_{1}+1],\dots,i_{m}\in[d_{m}+1]$ for which

$\displaystyle\operatorname{Tr}((z_{1,i_{1}}z_{1,i_{1}}^{\scriptscriptstyle\mathsf{T}})^{\otimes
d_{1}}\otimes\dots\otimes(z_{m,i_{m}}z_{m,i_{m}}^{\scriptscriptstyle\mathsf{T}})^{\otimes
d_{m}}M(p))\leq\frac{p_{\min}^{\mathbb{C}}}{c^{(1)}\cdots c^{(m)}}.$ (110)

Note that $c^{(j)}\geq c_{d_{j}}$ for each $j\in[m]$, by the proof of
Proposition 6. This completes the proof. ∎

We also require a slightly more general quantum de Finetti theorem.

######  Theorem 14 (More general quantum de Finetti theorem).

Let $k\geq\max_{j}d_{j}$ be an integer, and let
$v\in\mathcal{S}(S^{k}(\mathbb{C}^{n_{1}})\otimes\dots\otimes
S^{k}(\mathbb{C}^{n_{m}}))$. Then there exists a matrix

$\displaystyle\tau\in\mathrm{conv}\\{(u_{1}u_{1}^{*})^{\otimes
d_{1}}\otimes\dots\otimes(u_{m}u_{m}^{*})^{\otimes
d_{m}}:u_{j}\in\mathcal{S}(\mathbb{C}^{n_{j}})\\}$ (111)

for which

$\displaystyle\lVert\mspace{1.0mu}\operatorname{Tr}_{[d_{1}+1\cdot\cdot
k],\dots,[d_{m}+1\cdot\cdot
k]}(vv^{*})-\tau\mspace{1.0mu}\rVert_{1}\leq\frac{4d(\max_{j}n_{j}-1)}{k+1},$
(112)

where $d=d_{1}+\dots+d_{m}$, and $\operatorname{Tr}_{[d_{1}+1\cdot\cdot
k],\dots,[d_{m}+1\cdot\cdot k]}(vv^{*})$ denotes the partial trace over
$k-d_{j}$ copies of $\mathbb{C}^{n_{j}}$ for each $j\in[m]$.

This theorem can be seen as a special case of [KM09, Theorem III.3, Remark
III.4], or a slight generalization of [CKMR07, Theorem II.2’] and [Wat18,
Theorem 7.26]. We will prove the theorem as a corollary to [KM09, Theorem
III.3, Remark III.4].

###### Proof of Theorem 14.

Let

$\displaystyle\mathcal{A}$
$\displaystyle=S^{d_{1}}(\mathbb{C}^{n_{1}})\otimes\dots\otimes
S^{d_{m}}(\mathbb{C}^{n_{m}})$ (113) $\displaystyle\mathcal{B}$
$\displaystyle=S^{k-d_{1}}(\mathbb{C}^{n_{1}})\otimes\dots\otimes
S^{k-d_{m}}(\mathbb{C}^{n_{m}})$ (114) $\displaystyle\mathcal{C}$
$\displaystyle=S^{k}(\mathbb{C}^{n_{1}})\otimes\dots\otimes
S^{k}(\mathbb{C}^{n_{m}})$ (115) $\displaystyle\mathcal{X}$
$\displaystyle=u_{1}^{\otimes d_{1}}\otimes\dots\otimes u_{m}^{\otimes
d_{m}},$ (116)

where the $u_{j}\in\mathcal{S}(\mathbb{C}^{n_{j}})$ are arbitrary but fixed.
Then $\mathcal{C}\subseteq\mathcal{A}\otimes\mathcal{B}$ is an irreducible
subrepresentation (with multiplicity one) of the product unitary group
$U(\mathbb{C}^{n_{1}})\times\dots\times U(\mathbb{C}^{n_{m}})$. It is also
straightforward to check that the quantity $\delta(\mathcal{X})$ defined in
[KM09, Definition III.2] is equal to

$\displaystyle\frac{\dim(\mathcal{B})}{\dim(\mathcal{C})}$
$\displaystyle=\prod_{j=1}^{m}\frac{\binom{n_{j}+k-d_{j}-1}{k-d_{j}}}{\binom{n_{j}+k-1}{k}}$
(117)
$\displaystyle\geq\prod_{j=1}^{m}\left(1-\frac{d_{j}(n_{j}-1)}{k+1}\right)$
(118) $\displaystyle\geq 1-\frac{d(\max_{j}n_{j}-1)}{k+1},$ (119)

where the second line is a standard inequality that can be found e.g. in
[Wat18, Eq. (7.196)] The desired bound then follows directly from the bound
given in [KM09, Theorem III.3, Remark III.4] in terms of
$\delta(\mathcal{X})$. ∎

Now we can prove Theorem 12.

###### Proof of Theorem 12.

Note that

$\displaystyle\nu_{k}^{({\bf n},{\bf d})}=\max\\{\nu:M_{k}^{({\bf n},{\bf
d})}(p-\nu\;\;s_{{\bf n},{\bf d}})\succeq 0\\}.$ (120)

For the inequality $\nu_{k}^{({\bf n},{\bf d})}\leq p_{\min}^{({\bf n},{\bf
d})}$, note that since $M_{k}^{({\bf n},{\bf d})}(p-\nu_{k}^{({\bf n},{\bf
d})}s_{{\bf n},{\bf d}})\succeq 0$, we have

$\displaystyle\langle p,v_{1}^{\otimes 2d_{1}}\otimes\dots\otimes
v_{m}^{\otimes 2d_{m}}\rangle-\nu_{k}^{({\bf n},{\bf d})}$
$\displaystyle=\operatorname{Tr}((v_{1}v_{1}^{\scriptscriptstyle\mathsf{T}})^{\otimes
k}\otimes\dots\otimes(v_{m}v_{m}^{\scriptscriptstyle\mathsf{T}})^{\otimes
k}M_{k}^{({\bf n},{\bf d})}(p-\nu_{k}^{({\bf n},{\bf d})}\;\;s_{{\bf n},{\bf
d}}))\geq 0$ (121)

for any
$v_{1}\in\mathcal{S}({}^{n_{1}}),\dots,v_{m}\in\mathcal{S}({}^{n_{m}})$. For
the bound, let

$\displaystyle q_{k}=p-\nu_{k}^{({\bf n},{\bf d})}s_{{\bf n},{\bf d}}\in
S^{2d_{1}}({}^{n_{1}})\otimes\dots\otimes S^{2d_{m}}({}^{n_{m}}),$ (122)

and let $v\in\mathcal{S}(S^{2k}({}^{n_{1}})\otimes\dots\otimes
S^{2k}({}^{n_{m}})$ be a minimum (zero) eigenvector of $M_{k}^{({\bf n},{\bf
d})}(q_{k})$. By Theorem 14, there exists a matrix

$\displaystyle\tau\in\mathrm{conv}\\{(u_{1}u_{1}^{*})^{\otimes
d_{1}}\otimes\dots\otimes(u_{m}u_{m}^{*})^{\otimes
d_{m}}:u_{j}\in\mathcal{S}(\mathbb{C}^{n_{j}})\\}$ (123)

for which

$\displaystyle\lVert\mspace{1.0mu}\operatorname{Tr}_{[d_{1}+1\cdot\cdot
k],\dots,[d_{m}+1\cdot\cdot
k]}(vv^{\scriptscriptstyle\mathsf{T}})-\tau\mspace{1.0mu}\rVert_{1}\leq\frac{4d(\max_{j}n_{j}-1)}{k+1}.$
(124)

Let

$\displaystyle q_{k,\min}$ $\displaystyle=q_{k,\min}^{({\bf n},{\bf
d})}=\min_{v_{j}\in\mathcal{S}({}^{n_{j}})}\langle q_{k},v_{1}^{\otimes
2d_{1}}\otimes\dots\otimes v_{m}^{\otimes 2d_{m}}\rangle$ (125) $\displaystyle
q_{k,\min}^{\mathbb{C}}$
$\displaystyle=\min_{v_{j}\in\mathcal{S}(\mathbb{C}^{n_{j}})}\operatorname{Tr}((v_{1}v_{1}^{*})^{\otimes
d_{1}}\otimes\dots\otimes(v_{m}v_{m}^{*})^{\otimes d_{m}}{M(q_{k})}).$ (126)

Then

$\displaystyle q_{k,\min}^{\mathbb{C}}$
$\displaystyle\leq\operatorname{Tr}(M(q_{k})\tau)$ (127)
$\displaystyle=\operatorname{Tr}(M(q_{k})(\tau-\operatorname{Tr}_{[d_{1}+1\cdot\cdot
k],\dots,[d_{m}+1\cdot\cdot k]}(vv^{\scriptscriptstyle\mathsf{T}})))$ (128)
$\displaystyle\leq\lVert\mspace{1.0mu}M(q_{k})\mspace{1.0mu}\rVert_{\infty}\frac{4d(\max_{j}n_{j}-1)}{k+1}$
(129)
$\displaystyle\leq\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}\left(1+\kappa(M(s_{{\bf
n},{\bf d}}))\right)\frac{4d(\max_{j}n_{j}-1)}{k+1}.$ (130)

The first line follows from convexity. The second line follows from the chain
of equalities

$\displaystyle\operatorname{Tr}(M(q_{k})\operatorname{Tr}_{[d_{1}+1\cdot\cdot
k],\dots,[d_{m}+1\cdot\cdot k]}(vv^{\scriptscriptstyle\mathsf{T}}))$
$\displaystyle=\operatorname{Tr}((M(q_{k})\otimes\mathds{1}_{n_{1}}^{\otimes
k-d_{1}}\otimes\dots\otimes\mathds{1}_{n_{m}}^{\otimes
k-d_{m}})vv^{\scriptscriptstyle\mathsf{T}})$ (131)
$\displaystyle=\operatorname{Tr}(M_{k}(q_{k})vv^{\scriptscriptstyle\mathsf{T}})$
(132) $\displaystyle=0.$ (133)

The third line follows from Theorem 14 and the matrix norm inequality
$\operatorname{Tr}(AB)\leq\lVert\mspace{1.0mu}A\mspace{1.0mu}\rVert_{\infty}\lVert\mspace{1.0mu}B\mspace{1.0mu}\rVert_{1}$.
The fourth line follows from

$\displaystyle\lVert\mspace{1.0mu}M(q_{k})\mspace{1.0mu}\rVert_{\infty}$
$\displaystyle\leq\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}+\lvert\nu_{k}^{({\bf
n},{\bf d})}\rvert\lVert\mspace{1.0mu}M(s_{{\bf n},{\bf
d}})\mspace{1.0mu}\rVert_{\infty}$ (134)
$\displaystyle\leq\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}\left(1+\kappa(M(s_{{\bf
n},{\bf d}}))\right).$ (135)

Here, the first line is the triangle inequality, and the second line follows
from $\lVert\mspace{1.0mu}M(s_{{\bf n},{\bf
d}})\mspace{1.0mu}\rVert_{\infty}=\lambda_{\max}(M(s_{{\bf n},{\bf d}}))$ by
Proposition 4, and $\lvert\nu_{k}^{({\bf n},{\bf
d})}\rvert\leq\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}\lambda_{\min}(M(s_{{\bf
n},{\bf d}}))^{-1}$ since choosing $\nu$ equal to minus the righthand side
would guarantee $M(p)-\nu M(s_{{\bf n},{\bf d}})\succeq 0$. It follows from
Proposition 13 that

$\displaystyle p_{\min}^{({\bf n},{\bf d})}-\nu_{k}$
$\displaystyle=q_{k,\min}$ (136)
$\displaystyle\leq\frac{q_{k,\min}^{\mathbb{C}}}{c_{{\bf d}}}$ (137)
$\displaystyle\leq\lVert\mspace{1.0mu}M(p)\mspace{1.0mu}\rVert_{\infty}\left(1+\kappa(M(s_{{\bf
n},{\bf d}}))\right)\frac{4d(\max_{j}n_{j}-1)}{c_{{\bf d}}(k+1)}.$ (138)

This completes the proof. ∎

###  5.2 Examples: Biquadratic forms and the real spectral norm of a tensor

In this section we use our tensor optimization hierarchy and Theorem 12 to
give hierarchies of eigencomputations for two tasks: minimizing a biquadratic
form over the unit sphere, and computing the real spectral norm of a real
tensor.

######  Example 15 (Biquadratic forms and bihomogeneous forms).

A bihomogeneous form of degree $d$ is a polynomial $r(x,y)\in\real[x,y]_{2d}$
in two sets of variables $x=(x_{1},\dots,x_{n_{1}})$ and
$y=(y_{1},\dots,y_{n_{2}})$ for which there exists a tensor $p\in
S^{d}({}^{n_{1}})\otimes S^{d}({}^{n_{2}})$ that satisfies

$\displaystyle r(x,y)=\langle p,x^{\otimes d}\otimes y^{\otimes d}\rangle.$
(139)

A biquadratic form is a bihomogeneous form of degree $2$. We will focus on
biquadratic forms, but analogous results are easily shown for bihomogeneous
forms of higher degree. Let $q(x,y)\in\real[x,y]_{4}$ be a biquadratic form,
let

$\displaystyle
M_{k}=(\Pi_{n_{1},k}\otimes\Pi_{n_{2},k})(M(q)\otimes\mathds{1}_{n_{1}}^{\otimes
k-1}\otimes\mathds{1}_{n_{2}}^{\otimes
k-1})(\Pi_{n_{1},k}\otimes\Pi_{n_{2},k})$ (140)

and let $\nu_{k}=\lambda_{\min}(M_{k})$. By Theorem 12, the $\nu_{k}$ converge
to $\min_{x\in\mathcal{S}({}^{n_{1}}),y\in\mathcal{S}({}^{n_{2}})}q(x,y)$ from
below at a rate of $O(1/k)$.111111To see this, note that $M_{k}^{({\bf
n},(1,1))}(q)=M_{k}$ and $M_{k}^{({\bf n},(1,1))}(s_{{\bf
n},(1,1)})=\mathds{1}_{S^{k}({}^{n_{1}})}\otimes\mathds{1}_{S^{k}({}^{n_{2}})}$.
In particular, suppose we wish to determine whether $q$ is strictly positive
i.e. $q(x,y)>0$ for all $x,y\neq 0$. Our hierarchy establishes that this holds
if and only if $M_{k}$ is positive definite for some $k$. Note that

$\displaystyle\langle x^{\otimes k}\otimes y^{\otimes k},M_{k}\;\;x^{\otimes
k}\otimes y^{\otimes k}\rangle=q(x,y)\cdot s(x)^{k}\cdot s(y)^{k},$ (141)

so $M_{k}$ is a Gram matrix for $q$.121212Here we define the Gram matrix of a
bihomogeneous form $r(x,y)\in\real[x,y]_{2k}$ as a matrix
$M\in\mathrm{Hom}(S^{k}({}^{n_{1}})\otimes S^{k}({}^{n_{2}}))$ for which
$r(x,y)=\langle x^{\otimes k}\otimes y^{\otimes k},M\;x^{\otimes k}\otimes
y^{\otimes k}\rangle$. In particular, a biquadratic form is strictly positive
on non-zero inputs if and only if $q(x,y)\cdot s(x)^{k}\cdot s(y)^{k}$ admits
a positive definite Gram matrix for some $k$.

######  Example 16 (The real spectral norm of a tensor).

Let $p\in{}^{n_{1}}\otimes\dots\otimes{}^{n_{m}}$ be a tensor. Assume without
loss of generality that $\lVert\mspace{1.0mu}p\mspace{1.0mu}\rVert_{2}=1$,
where $\lVert\mspace{1.0mu}\cdot\mspace{1.0mu}\rVert_{2}$ denotes the
Euclidean norm. The (real) spectral norm of $p$ is defined as

$\displaystyle\lVert\mspace{1.0mu}p\mspace{1.0mu}\rVert_{\sigma,\real}:=\max_{v_{j}\in\mathcal{S}({}^{n_{j}})}\lvert\langle
p,v_{1}\otimes\dots\otimes v_{m}\rangle\rvert.$ (142)

We can use our hierarchy to compute the spectral norm of $p$ as follows. First
note that

$\displaystyle-\lVert\mspace{1.0mu}p\mspace{1.0mu}\rVert_{\sigma,\real}=\min_{v_{j}\in\mathcal{S}({}^{n_{j}})}\langle
p,v_{1}\otimes\dots\otimes v_{m}\rangle,$ (143)

so it suffices to compute the righthand side of this expression. Let

$\displaystyle q=p\otimes e_{n_{1}+1}\otimes\dots\otimes
e_{n_{m}+1}\in\bigg{(}\bigotimes_{j=1}^{m}{}^{n_{j}+1}\bigg{)}^{\otimes 2},$
(144)

where we embed each ${}^{n_{j}}$ into the first $n_{j}$ coordinates of
${}^{n_{j}+1}$. Let

$\displaystyle
r=(\Pi_{n_{1}+1,k}\otimes\dots\otimes\Pi_{n_{m}+1,k})(\sigma\cdot q)\in
S^{2}({}^{n_{1}+1})\otimes\dots\otimes S^{2}({}^{n_{m}+1}),$ (145)

where $\sigma\in S_{2m}$ is the permutation that sends $(1,2,\dots,2m)$ to
$(1,m+1,2,m+2,\dots,m,2m)$. Direct calculation shows that
$\lVert\mspace{1.0mu}r\mspace{1.0mu}\rVert_{2}=2^{-m/2}$. By Proposition 11 it
holds that

$\displaystyle 2^{-m}\;\cdot\;\min_{v_{j}\in\mathcal{S}({}^{n_{j}})}\langle
p,v_{1}\otimes\dots\otimes
v_{m}\rangle=\min_{v_{j}\in\mathcal{S}({}^{n_{j}+1})}\langle r,v_{1}^{\otimes
2}\otimes\dots\otimes v_{m}^{\otimes 2}\rangle.$ (146)

Our hierarchy can be used to compute the righthand side of (146) as follows.
Let $M(r)\in\mathrm{Hom}(\otimes_{j}{}^{n_{j}+1})$ be the tensor $r$ after the
isomorphism
$\otimes_{j}S^{2}({}^{n_{j}+1})\cong\mathrm{Hom}(\otimes_{j}{}^{n_{j}+1})$.
For each $k\in\mathbb{N}$, let

$\displaystyle
M_{k}=(\Pi_{n_{1}+1,k}\otimes\dots\otimes\Pi_{n_{m}+1,k})(M(r)\otimes\mathds{1}_{n_{1}+1}^{\otimes
k-1}\otimes\dots\otimes\mathds{1}_{n_{m}+1}^{\otimes
k-1})(\Pi_{n_{1}+1,k}\otimes\dots\otimes\Pi_{n_{m}+1,k}).$ (147)

Then by our Theorem 12, the minimum eigenvalues
$\nu_{k}:=\lambda_{\min}(M_{k})$ converge to the righthand side of (146) from
below at a rate of $O(1/k)$ (for similar reasons as in Footnote 11). More
precisely, we have the following convergence guarantee:

######  Theorem 17 (Convergence guarantee for spectral norm).

For each $k\in\mathbb{N}$ let $\mu_{k}=-2^{m}\lambda_{\min}(M_{k})$. Then
$\mu_{k}\geq\lVert\mspace{1.0mu}p\mspace{1.0mu}\rVert_{\sigma,\real}$ for all
$k$, and

$\displaystyle\mu_{k}-\lVert\mspace{1.0mu}p\mspace{1.0mu}\rVert_{\sigma,\real}$
$\displaystyle\leq
2^{m}\cdot\lVert\mspace{1.0mu}M(r)\mspace{1.0mu}\rVert_{\infty}\left(1+\kappa(M(s_{{\bf
n},1^{(m)}}))\right)\frac{4m(\max_{j}n_{j}-1)}{c_{(1^{(m)})}(k+1)}$ (148)
$\displaystyle\leq\frac{2^{m/2+3}m(\max_{j}n_{j}-1)}{k+1}$ (149)
$\displaystyle=O\left(\frac{1}{k}\right),$ (150)

where $1^{(m)}=(1,\dots,1)$ ($m$ times). In particular,
$\lim_{k\rightarrow\infty}\kappa_{k}=\lVert\mspace{1.0mu}p\mspace{1.0mu}\rVert_{\sigma,\real}$.

###### Proof.

For the first line in (148), note that

$\displaystyle\mu_{k}-\lVert\mspace{1.0mu}p\mspace{1.0mu}\rVert_{\sigma,\real}$
$\displaystyle=-2^{m}\nu_{k}+\min_{v_{j}\in\mathcal{S}({}^{n_{j}})}\langle
p,v_{1}\otimes\dots\otimes v_{m}\rangle$ (151)
$\displaystyle=-2^{m}\nu_{k}+2^{m}\min_{v_{j}\in\mathcal{S}({}^{n_{j}+1})}\langle
r,v_{1}^{\otimes 2}\otimes\dots\otimes v_{m}^{\otimes 2}\rangle$ (152)
$\displaystyle=2^{m}(r_{\min}^{({\bf n},(1^{(m)}))}-\nu_{k}).$ (153)

So the first line follows from Theorem 12. The second line follows from
$c_{(1^{(m)})}=1$, ${\kappa(M(s_{{\bf n},1^{(m)}}))=1}$, and
$\lVert\mspace{1.0mu}M(r)\mspace{1.0mu}\rVert_{\infty}\leq\lVert\mspace{1.0mu}r\mspace{1.0mu}\rVert_{2}=2^{-m/2}$.
This completes the proof. ∎

##  6 Constrained polynomial optimization

To obtain our hierarchy for computing the minimum value $p_{\min}$ of a real
polynomial $p$ over the real sphere, we showed that it was related to the
minimum value $p_{\min}^{\mathbb{C}}$ of a certain minimization problem over
the complex sphere (Proposition 6), and invoked the quantum de Finetti theorem
for this complex problem (Theorem 7). In more details, we proved that
$p_{\min}^{\mathbb{C}}\leq p_{\min}\leq\frac{1}{c_{d}}p_{\min}^{\mathbb{C}}$
for a constant $c_{d}$; in particular,

$\displaystyle p_{\min}=0\iff p_{\min}^{\mathbb{C}}=0.$ (154)

In Section 5 we generalized these results to obtain hierarchies of
eigencomputations for a certain class of constrained polynomial optimization
problems: minimizing the inner product between a real tensor and an element of
the real spherical Segre-Veronese variety.

In this section, we consider whether our hierarchy can be generalized to
handle other polynomial constraints. We focus here on hierarchies of
eigencomputations (see the end of this section for two natural choices of
hierarchies which are not eigencomputations). We first note that the complex
minimization hierarchy can indeed be generalized, but find an example where
the real minimum is zero but the complex minimum is non-zero (i.e. the
corresponding generalization of (154) does not hold). This indicates to us
that a corresponding generalization of Proposition 6 seems non-trivial. We
will require a bit of algebraic geometry in this section; we refer the reader
to [Har13] for background.

Let us consider constrained optimization problems of the form

$\displaystyle p_{q,\min}=\min_{\begin{subarray}{c}x\in\mathcal{S}({}^{n})\\\
q_{1}(x)=\dots=q_{\ell}(x)=0\end{subarray}}p(x),$ (155)

where $p\in\real[x]_{2d}$ and $q_{1},\dots,q_{\ell}\in\real[x]$ are
homogeneous polynomials.131313One can replace the multiple equality
constraints $q_{1}(x)=\dots=q_{\ell}(x)=0$ with the single constraint
$q(x):=q_{1}(x)^{2}+\dots+q_{\ell}(x)^{2}=0.$ However we will soon consider a
complex analogue to this problem for which this cannot necessarily be done. We
therefore stick with multiple equality constraints throughout to keep the
notation uniform. Identifying the polynomials $q_{i}$ with symmetric tensors,
let $I=\langle q_{1},\dots,q_{\ell}\rangle\subseteq S({}^{n})$ be the ideal
generated by $q_{1},\dots,q_{\ell}$ in the symmetric algebra
$S({}^{n}):=\bigoplus_{d\geq 0}S^{d}({}^{n})$. For each positive integer $k$,
let $I_{k}\subseteq S^{k}({}^{n})$ be the degree-$k$ part of $I$, and let
$\Pi_{n,k,I}\in\mathrm{Hom}(({}^{n})^{\otimes k})$ be the orthogonal
projection onto the orthogonal complement of $I_{k}$. Note that
$\Pi_{n,k,0}=\Pi_{n,k}$ is the orthogonal projection onto $S^{k}({}^{n})$.

For a field $\mathbb{F}\in\\{\real,\mathbb{C}\\}$ and subset
$J\subseteq\mathbb{F}[x]$, we let

$\displaystyle V_{\mathbb{F}}(J)$
$\displaystyle=\\{x\in\mathbb{F}^{n}:q(x)=0\quad\text{for all}\quad q\in
J\\}.$ (156)

The sets $V_{\mathbb{F}}(J)\subseteq\mathbb{F}^{n}$ form the closed sets in
the Zariski topology on $\mathbb{F}^{n}$. We denote the Zariski closure of a
set $S\subseteq\mathbb{F}^{n}$ by $\mathrm{Cl}_{\mathbb{F}}(S)$. An
$\mathbb{F}$-variety is a set of the form $V_{\mathbb{F}}(J)$ for some
$J\subseteq\mathbb{F}[x]$.

The following result gives a hierarchy of minimum eigenvalue computations for
solving a certain complex analogue to the constrained minimization problem
(155).

######  Theorem 18.

Let $M\in\mathrm{Hom}(S^{d}({}^{n}))$ be any Gram matrix of $p$ for which
$M=M^{\scriptscriptstyle\mathsf{T}}$. For each integer $k\geq d$, let
$\nu_{k}=\lambda_{\min}(M_{k})$, where

$\displaystyle M_{k}=\Pi_{n,k,I}(M\otimes\mathds{1}_{n}^{\otimes
k-d})\Pi_{n,k,I}.$ (157)

Then $\nu_{d}\leq\nu_{d+1}\leq\nu_{d+2}\leq\dots$, and

$\displaystyle\lim_{k\rightarrow\infty}\nu_{k}=\min_{\begin{subarray}{c}v\in\mathcal{S}(\mathbb{C}^{n})\\\
q_{1}(v)=\dots=q_{\ell}(v)=0\end{subarray}}\operatorname{Tr}((vv^{*})^{\otimes
d}M).$ (158)

In the unconstrained case $I=0$, Theorem 18 follows from the quantum de
Finetti theorem (Theorem 7). A proof of Theorem 18 in full generality will be
presented in the forthcoming work [DJLV23].

######  Proposition 19.

Let

$\displaystyle p(x,y,z)$ $\displaystyle=xz\in\real[x,y,z]_{2},$ (159)
$\displaystyle q(x,y,z)$
$\displaystyle=x^{2}+y^{2}-\frac{1}{\sqrt{3}}xz\in\real[x,y,z]_{2}.$ (160)

Then

$\displaystyle
p_{q,\min}=0>-\frac{1}{2\sqrt{3}}\geq\min_{\begin{subarray}{c}v\in\mathcal{S}(\mathbb{C}^{3})\\\
q(v)=0\end{subarray}}\operatorname{Tr}(vv^{*}M(p)).$ (161)

This proposition indicates to us that there is no obvious generalization of
Proposition 6, because in particular no natural generalization of (154) seems
to hold. The example provided by this proposition is non-trivial in two ways:

  1. 1.

For the general constrained polynomial optimization problem (155) it always
holds that

$\displaystyle
p_{q,\min}\geq\min_{\begin{subarray}{c}v\in\mathcal{S}(\mathbb{C}^{n})\\\
q_{1}(v)=\dots=q_{\ell}(v)=0\end{subarray}}\operatorname{Tr}((vv^{*})^{\otimes
d}M)$ (162)

for any symmetric ($M=M^{{\scriptscriptstyle\mathsf{T}}}$) Gram matrix $M$,
since $V_{\mathbb{C}}(q)\cap{}^{n}=V(q)$. It is natural to ask if one could
get equality in the above proposition by instead minimizing the righthand side
over a smaller variety in $\mathbb{C}^{n}$ whose intersection with n still
equals $V(q)$ (optimizing over larger varieties can only make the inequality
worse). This is not the case, since for $q$ defined as in (159) it holds that
$\mathrm{Cl}_{\mathbb{C}}(V(q))=V_{\mathbb{C}}(q)$ i.e. $V_{\mathbb{C}}(q)$ is
the smallest $\mathbb{C}$-variety containing $V(q)$. Indeed, it is easily
checked that $q$ is irreducible over $\mathbb{C}$ and that $V_{\mathbb{C}}(q)$
contains at least one real smooth point (the only singular point of
$V_{\mathbb{C}}(q)$ is $(0,0,0)$). Hence
$\mathrm{Cl}_{\mathbb{C}}(V(q))=V_{\mathbb{C}}(q)$ by [Man20, Theorem
2.2.9(2)].

  2. 2.

It is also natural to ask if equality holds under a different choice of Gram
matrix for $p$ that satisfies $M=M^{{\scriptscriptstyle\mathsf{T}}}$ (so that
Theorem 18 applies). This is not the case because when $p$ is quadratic,
$M(p)$ is the unique Gram matrix for $p$ satisfying this property.

In short, there does not seem to be an obvious way to compute $p_{q,\min}$ by
some natural adaptation of the complex problem.

###### Proof of Proposition 19.

Let us first verify that $p_{q,\min}=0$. It is clear that $p_{q,\min}\geq 0$
because any solution must satisfy $xz=\sqrt{3}(x^{2}+y^{2})\geq 0$. For the
equality to zero, note that $q(0,0,1)=p(0,0,1)=0$. For the last inequality,
consider the point
$v=(\frac{1}{\sqrt{6}},\frac{i}{\sqrt{3}},-\frac{1}{\sqrt{2}})^{\scriptscriptstyle\mathsf{T}}\in\mathcal{S}(\mathbb{C}^{3})$,
which is a zero of $q$. Note that

$\displaystyle M(p)=\begin{bmatrix}0&0&1/2\\\ 0&0&0\\\ 1/2&0&0\end{bmatrix},$
(163)

and $\operatorname{Tr}(vv^{*}M(p))=-\frac{1}{2\sqrt{3}}$. This completes the
proof. ∎

We conclude this section by noting that there are two other natural ways to
adapt our hierarchy to handle constraints, neither of which produce
hierarchies of eigencomputations: First, one can use the method described in
[AH19] for adapting certificates of global positivity to perform constrained
polynomial optimization, but each step of the resulting hierarchy would
require the use of bisection. Second, one could simply replace the sum-of-
squares polynomials that appear in standard positivstellensatze with
polynomials that our hierarchy certifies to be globally non-negative at some
level. For example, a special case of Putinar’s positivestellensatz says that
a polynomial $p(x)$ is strictly positive on $V(q)$ if and only if there exists
a sum-of-squares polynomial $\sigma(x)$ and a polynomial $h(x)$ for which
$p(x)=\sigma(x)+h(x)q(x)$ [Put93]. Instead of searching for a sum-of-squares
polynomial $\sigma$, one could impose that some fixed level of our hierarchy
certifies global non-negativity of $\sigma$. This would give a sequence of
semidefinite programs, indexed by the degrees of $\sigma$ and $h$, and by the
level of our hierarchy that we consider, which successfully finds such a pair
$(\sigma,h)$ in some high enough degrees and level if and only if $p(x)$ is
strictly positive on $V(q)$.

##  7 Acknowledgments

We thank Hamza Fawzi, Monique Laurent, Tim Netzer, Bruce Reznick, Jurij Volcic
and Timo de Wolff for enlightening discussions. N.J. was supported by NSERC
Discovery Grant RGPIN2022-04098. B.L. acknowledges that this material is based
upon work supported by the National Science Foundation under Award No.
DMS-2202782. A.V. was supported by the National Science Foundation under Grant
Nos. CCF-1652491, CCF-1934931, ECCS-2216970. Any opinions, findings, and
conclusions or recommendations expressed in this material are those of the
authors and do not necessarily reflect the views of the National Science
Foundation.

## References

  * [AH19] Amir Ali Ahmadi and Georgina Hall.  On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity.  Mathematics of Operations Research, 44(4):1192–1207, 2019.
  * [AM19] Amir Ali Ahmadi and Anirudha Majumdar.  DSOS and SDSOS optimization: More tractable alternatives to sum of squares and semidefinite optimization.  SIAM Journal on Applied Algebra and Geometry, 3(2):193–230, 2019\.
  * [BBH+12] Boaz Barak, Fernando GSL Brandao, Aram W Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou.  Hypercontractivity, sum-of-squares proofs, and their applications.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 307–326, 2012.
  * [BGG+17] V. Bhattiprolu, M. Ghosh, V. Guruswami, E. Lee, and M. Tulsiani.  Weak decoupling, polynomial folds and approximate optimization over the sphere.  In IEEE Symposium on Foundations of Computer Science (FOCS), pages 1008–1019, 2017.
  * [BV09] S. Charles Brubaker and Santosh S. Vempala.  Random tensors and planted cliques.  In Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX ’09 / RANDOM ’09, pages 406–419, Berlin, Heidelberg, 2009. Springer-Verlag.
  * [CKMR07] Matthias Christandl, Robert König, Graeme Mitchison, and Renato Renner.  One-and-a-half quantum de finetti theorems.  Communications in mathematical physics, 273(2):473–498, 2007.
  * [DJLV23] Harm Derksen, Nathaniel Johnston, Benjamin Lovitz, and Aravindan Vijayaraghavan.  Beyond separability: a generalization of the symmetric extensions hierarchy.  In preparation, 2023+.
  * [DK08] Etienne De Klerk.  The complexity of optimizing over a simplex, hypercube or sphere: a short survey.  Central European Journal of Operations Research, 16:111–125, 2008\.
  * [dKLP05] Etienne de Klerk, Monique Laurent, and Pablo Parrilo.  On the equivalence of algebraic approaches to the minimization of forms on the simplex.  Positive Polynomials in Control, pages 121–132, 2005.
  * [DPS04] A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri.  A complete family of separability criteria.  Physical Review A, 69:022308, 2004.
  * [DW12] Andrew C Doherty and Stephanie Wehner.  Convergence of sdp hierarchies for polynomial optimization on the hypersphere.  arXiv preprint arXiv:1210.5048, 2012.
  * [FF21] Kun Fang and Hamza Fawzi.  The sum-of-squares hierarchy on the sphere and applications in quantum information theory.  Mathematical Programming, 190:331–360, 2021.
  * [FK08] Alan M. Frieze and Ravi Kannan.  A new approach to the planted clique problem.  In Foundations of Software Technology and Theoretical Computer Science, 2008.
  * [Har13] Joe Harris.  Algebraic Geometry: A First Course.  Graduate Texts in Mathematics. Springer New York, 2013.
  * [HSSS16] Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer.  Fast spectral algorithms from sum-of-squares proofs: Tensor decomposition and planted sparse vectors.  In ACM Symposium on Theory of Computing (STOC), 2016.
  * [Joh16] Nathaniel Johnston.  QETLAB: A MATLAB toolbox for quantum entanglement.  https://qetlab.com, 2016.  See the “PolynomialOptimize” function in particular: https://qetlab.com/PolynomialOptimize.
  * [KM09] Robert Koenig and Graeme Mitchison.  A most compendious and facile quantum de finetti theorem.  Journal of Mathematical Physics, 50(1):012105, 2009.
  * [Lau09] Monique Laurent.  Sums of Squares, Moment Matrices and Optimization Over Polynomials, pages 157–270.  Springer New York, 2009.
  * [Lau19] Monique Laurent.  Notes on the paper: “Convergence of SDP hierarchies for polynomial optimization on the hypersphere”, by A.C Doherty and S. Wehner.  https://homepages.cwi.nl/ monique/Doherty-Wehner-notesv2.pdf, 2019.
  * [LSY98] R. B. Lehoucq, D. C. Sorensen, and C. Yang.  ARPACK Users’ Guide.  Society for Industrial and Applied Mathematics, 1998.
  * [Man20] Frédéric Mangolte.  Real algebraic varieties.  Springer, 2020.
  * [Mar08] Murray Marshall.  Positive polynomials and sums of squares.  Number 146. American Mathematical Society, 2008.
  * [N+03] Jurij Evgenevič Nesterov et al.  Random walk in a simplex and quadratic optimization over convex polytopes.  Technical report, Center for Operations Research and Econometrics, 2003\.
  * [Net16] Tim Netzer.  Real algebraic geometry and its applications.  arXiv preprint arXiv:1606.07284, 2016.
  * [Par03] Pablo A Parrilo.  Semidefinite programming relaxations for semialgebraic problems.  Mathematical programming, 96:293–320, 2003.
  * [Put93] Mihai Putinar.  Positive polynomials on compact semi-algebraic sets.  Indiana University Mathematics Journal, 42(3):969–984, 1993.
  * [Rez95] Bruce Reznick.  Uniform denominators in Hilbert’s seventeenth problem.  Mathematische Zeitschrift, 220(1):75–97, 1995.
  * [Rez13] Bruce Reznick.  On the length of binary forms.  In Quadratic and higher degree forms, pages 207–232. Springer, 2013\.
  * [RM14] Emile Richard and Andrea Montanari.  A statistical model for tensor PCA.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
  * [SS17] Tselil Schramm and David Steurer.  Fast and robust tensor decomposition with applications to dictionary learning.  In Conference on Learning Theory, pages 1760–1793, 2017.
  * [Ste02] G. W. Stewart.  A Krylov–Schur algorithm for large eigenproblems.  SIAM Journal on Matrix Analysis and Applications, 23(3):601–614, 2002.
  * [Wat18] J. Watrous.  The Theory of Quantum Information.  Cambridge University Press, 2018.

##  Appendix A Formula for $M_{k}(p)$

In this section we derive an explicit formula for the coordinates of
$M_{k}(p)=\Pi_{n,k}(M(p)\otimes\mathds{1}_{n}^{\otimes{k-d}})\Pi_{n,k}$. We
make the following definitions.

  1. 1.

For positive integers $n$ and $d$, let $[n]^{\vee
d}=\\{(i_{1},\dots,i_{d})\in[n]^{\times d}:1\leq i_{1}\leq\dots\leq i_{d}\leq
n\\}$ be the non-decreasing $d$-tuples of integers from 1 to $n$.

  2. 2.

For $I\in[n]^{\vee d}$, $j\in[n]$, let $r_{j}^{I}$ be the number of times $j$
appears in $I$.

  3. 3.

For $I\in[n]^{\vee d}$, let $f(I)=(d!r_{1}^{I}!\cdots r_{n}^{I}!)^{1/2}$.

  4. 4.

For $I\in[n]^{\vee d}$, let $m(I)=\frac{d!}{r_{1}^{I}!\cdots r_{n}^{I}!}$ be
the multinomial coefficient.

  5. 5.

For non-negative integers $a$ and $b$, let
$a^{\underline{b}}=\prod_{i=0}^{b-1}(a-i)$ be the falling factorial.

  6. 6.

For a positive integer $k\geq d$ and tuples $I\in[n]^{\vee k}$,
$H\in[n]^{\vee(k-d)}$, let
$g(I,H)=(r_{1}^{I})^{\underline{r_{1}^{H}}}\cdots(r_{n}^{I})^{\underline{r_{n}^{H}}}$.

  7. 7.

For $I,J\in[n]^{\times k}$, we say $I\sim J$ if $I=J$ up to reordering
indices. We extend all of the above definitions to tuples in $[n]^{\times k}$
by reordering indices. Let $\delta_{I,J}$ equal 1 if $I\sim J$ and zero
otherwise.

We will use the orthonormal basis $\\{e_{I}:I\in[n]^{\vee d}\\}$ for
$S^{d}({}^{n})$, where

$\displaystyle e_{I}:=\frac{1}{f(I)}\sum_{\sigma\in
S_{d}}e_{i_{\sigma(1)}}\otimes\dots\otimes e_{i_{\sigma(d)}}.$ (164)

For each $I\in[n]^{\vee d}$, let $f_{I}=f(I)e_{I}$.

######  Proposition 20.

For $I,L\in[n]^{\vee k}$, let $M_{k}(p)_{I,L}$ be the $(I,L)$-coordinate of
$M_{k}(p)$ in the basis $\\{e_{I}:I\in[n]^{\vee k}\\}$. It holds that

$\displaystyle M_{k}$
$\displaystyle(p)_{I,L}=(d!)^{2}f(I)^{-1}f(L)^{-1}\sum_{J,K\in[n]^{\vee
d}}\alpha_{(J,K)}m((J,K))^{-1}\sum_{H\in[n]^{\vee
k-d}}\delta_{I,(J,H)}\delta_{L,(K,H)}m(H)g(I,H)g(L,H).$ (165)

In particular, for $J,K\in[n]^{\vee d}$ we have

$\displaystyle
M(p)_{J,K}=\alpha_{(J,K)}\;(d!)^{2}\;m((J,K))^{-1}\;f(J)^{-1}\;f(K)^{-1}.$
(166)

###### Proof.

First let’s write down the coordinates of $M(p)=M_{d}(p)$. If

$\displaystyle p=\sum_{I\in[n]^{\vee 2d}}\alpha_{I}x_{i_{1}}\cdots
x_{i_{2d}},$ (167)

then after the isomorphism $\real[x]_{2d}\cong S^{2d}({}^{n})$ we obtain

$\displaystyle\vec{p}=\frac{1}{(2d)!}\sum_{I\in[n]^{\vee 2d}}\alpha_{I}f_{I}.$
(168)

Note that

$\displaystyle f_{I}$ $\displaystyle=(\Pi_{n,d}\otimes\Pi_{n,d})f_{I}$ (169)
$\displaystyle=(\Pi_{n,d}\otimes\Pi_{n,d})\sum_{\sigma\in
S_{2d}}e_{i_{\sigma(1)}}\otimes\dots\otimes e_{i_{\sigma(2d)}}$ (170)
$\displaystyle=\frac{1}{(d!)^{2}}\sum_{\sigma\in
S_{2d}}f_{\sigma(I)_{[d]}}\otimes f_{\sigma(I)_{[d+1..2d]}}$ (171)
$\displaystyle=\frac{1}{(d!)^{2}}\sum_{\begin{subarray}{c}J,K\in[n]^{\vee
d}\\\ (J,K)\sim I\end{subarray}}\mu_{I,J}f_{J}\otimes f_{K}$ (172)
$\displaystyle=\sum_{\begin{subarray}{c}J,K\in[n]^{\vee d}\\\ (J,K)\sim
I\end{subarray}}\binom{r_{1}^{I}}{r_{1}^{J}}\cdots\binom{r_{n}^{I}}{r_{n}^{J}}f_{J}\otimes
f_{K}$ (173)

where $\sigma(I)_{[d]}$ is the first $d$ elements of $\sigma(I)$;
$\sigma(I)_{[d+1..2d]}$ is the last $d$ elements of $\sigma(I)$; and
$\mu_{I,J}$ is the number of permutations $\sigma\in S_{2d}$ for which
$\sigma(I)_{[d]}\sim J$. The last line follows from the fact that

$\displaystyle\mu_{I,J}=(d!)^{2}\binom{r_{1}^{I}}{r_{1}^{J}}\cdots\binom{r_{n}^{I}}{r_{n}^{J}}.$
(174)

This formula holds because, for each $j$, $\sigma$ can take $r_{j}^{J}$
elements from $r_{j}^{I}$ to $[d]$, and permute the resulting $d$ elements
arbitrarily, and also permute the leftover $d$ elements arbitrarily. This
gives

$\displaystyle\vec{p}$ $\displaystyle=\frac{1}{(2d)!}\sum_{I\in[n]^{\vee
2d}}\alpha_{I}\sum_{\begin{subarray}{c}J,K\in[n]^{\vee d}\\\ (J,K)\sim
I\end{subarray}}\binom{r_{1}^{I}}{r_{1}^{J}}\cdots\binom{r_{n}^{I}}{r_{n}^{J}}f_{J}\otimes
f_{K}$ (175) $\displaystyle=\frac{1}{(2d)!}\sum_{I\in[n]^{\vee
2d}}\alpha_{I}\sum_{\begin{subarray}{c}J,K\in[n]^{\vee d}\\\ (J,K)\sim
I\end{subarray}}f(J)f(K)\binom{r_{1}^{I}}{r_{1}^{J}}\cdots\binom{r_{n}^{I}}{r_{n}^{J}}f_{J}\otimes
f_{K}$ (176)

Thus,

$\displaystyle M(p)_{J,K}$
$\displaystyle=\alpha_{(J,K)}\frac{1}{(2d)!}f(J)f(K)\binom{r_{1}^{I}}{r_{1}^{J}}\cdots\binom{r_{n}^{I}}{r_{n}^{J}}$
(177)
$\displaystyle=\alpha_{(J,K)}\;(d!)^{2}\;m((J,K))^{-1}\;f(J)^{-1}\;f(K)^{-1}.$
(178)

Now let’s compute the coordinates of $M_{k}(p)$. First note that for
$I,L\in[n]^{\vee k}$, $J,K\in[n]^{\vee d}$, and $H\in[n]^{\vee{k-d}}$, we have

$\displaystyle e_{I}^{*}(e_{J}\otimes e_{h_{1}}\otimes\dots\otimes
e_{h_{k-d}})=\delta_{I,(J,H)}f(I)^{-1}f(J)g(I,H),$ (179)

and

$\displaystyle e_{I}^{*}(e_{J}e_{K}^{*}\otimes\mathds{1}_{n}^{\otimes
k-d})e_{L}$ $\displaystyle=\sum_{H\in[n]^{\vee
k-d}}\delta_{I,(J,H)}\delta_{L,(K,H)}\;m(H)\;e_{I}^{*}(e_{J}\otimes
e_{h_{1}}\otimes\dots\otimes e_{h_{k-d}})(e_{K}^{*}\otimes
e_{h_{1}}^{*}\otimes\dots\otimes e_{h_{k-d}}^{*})e_{L}$ (180)
$\displaystyle=f(I)^{-1}f(J)f(K)f(L)^{-1}\sum_{H\in[n]^{\vee
k-d}}\delta_{I,(J,H)}\delta_{L,(K,H)}m(H)g(I,H)g(L,H).$ (181)

Thus,

$\displaystyle M_{k}$
$\displaystyle(p)_{I,L}=e_{I}^{*}\left(\sum_{J,K\in[n]^{\vee
d}}M(p)_{(J,K)}e_{J}e_{K}^{*}\otimes\mathds{1}_{n}^{\otimes k-d}\right)e_{L}$
(182) $\displaystyle=(d!)^{2}f(I)^{-1}f(L)^{-1}\sum_{J,K\in[n]^{\vee
d}}\alpha_{(J,K)}m((J,K))^{-1}\sum_{H\in[n]^{\vee
k-d}}\delta_{I,(J,H)}\delta_{L,(K,H)}m(H)g(I,H)g(L,H).$ (183)

This completes the proof. ∎