© 2023 \mathrm{S}\mathrm{o}\mathrm{c}\mathrm{i}\mathrm{e}\mathrm{t}\mathrm{y} \mathrm{f}\mathrm{o}\mathrm{r} \mathrm{I}\mathrm{n}\mathrm{d}\mathrm{u}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{l} \mathrm{a}\mathrm{n}\mathrm{d} \mathrm{A}\mathrm{p}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{d} \mathrm{M}\mathrm{a}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{c}\mathrm{s}Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy\mathrm{S}\mathrm{I}\mathrm{A}\mathrm{M} \mathrm{J}. \mathrm{O}\mathrm{P}\mathrm{T}\mathrm{I}\mathrm{M}.
\mathrm{V}\mathrm{o}\mathrm{l}. 33, \mathrm{N}\mathrm{o}. 3, \mathrm{p}\mathrm{p}. 2041--2061

LOW-RANK UNIVARIATE SUM OF SQUARES HAS NO SPURIOUS
LOCAL MINIMA*
BENO\^IT LEGAT\dagger  , CHENYANG YUAN\dagger  , AND PABLO PARRILO\dagger Abstract. We study the problem of decomposing apolynomial \bigm\| p into a sum of r squares by\bigm\| \sum 2minimizing a quadratically penalized objective fp (u) = \bigm\|  ri=1 u2i  -  p\bigm\|  . This objective is nonconvex and is equivalent to the rank-r Burer--Monteiro factorization of a semidefinite program (SDP)
encoding the sum of squares decomposition. We show that for all univariate polynomials p, if r \geq  2,
then fp (u) has no spurious second-order critical points, showing that all local optima are also global
optima. This is in contrast to previous work showing that for general SDPs, in addition to genericity
conditions, r has to be roughly the square root of the number of constraints (the degree of p) for
there to be no spurious second-order critical points. Our proof uses tools from computational algebraic geometry and can be interpreted as constructing a certificate using the first- and second-ordernecessary conditions. We also show that by choosing a norm based on sampling equally spaced
points on the circle, the gradient \nabla fp can be computed in nearly linear time using fast Fourier transforms. Experimentally we demonstrate that this method has very fast convergence using first-order
optimization algorithms such as L-BFGS, with near-linear scaling to million-degree polynomials.
Key words. nonconvex optimization, sum of squares, trigonometric polynomials, Burer-Monteiro method, global landscape, semidefinite programming
MSC codes. 90C23, 90C26, 90C22
DOI. 10.1137/22M1516208

1. Introduction. Burer--Monteiro factorization [9] is a methodology to solve
large-scale semidefinite programs (SDPs) by replacing positive semidefinite (PSD)
variables X \succeq  0 with a factorization X = U U \top  . This automatically enforces the
PSD constraint and lets us find low-rank solutions by choosing the rank of the newvariable U . In addition, this factorization results in a nonlinear optimization problem
that can be solved with first-order methods with fast per-iteration times, especiallywhen rank(U ) is small. However, the resulting problem is nonconvex, so these methods
may get stuck in local optima. We show that this will not happen to the SDP finding
the sum of squares decomposition of univariate polynomials; in this setting all local
optima are also global.
In this work we study SDPs arising from sum of squares optimization [32]. The
ability to represent the cone of sum of squares polynomials as a SDP enables many
applications in polynomial optimization, control, and relaxations of combinatorial
problems [27, 5]. To determine if a polynomial p(x) \in  \BbbR [x]2d is a sum of squares, itsuffices to find a feasible solution to the following SDP:
(1.1)

p(x) = b(x)\top  Xb(x),X \succeq  0,* Received by the editors August 16, 2022; accepted for publication (in revised form) April 18,
2023; published electronically August 8, 2023.
https://doi.org/10.1137/22M1516208
Funding: The first author was supported by a BAEF Postdoctoral Fellowship and the NSF
grant OAC-1835443. The second author was supported by the NSF grant CCF-1565235 and AFOSR
grant FA8750-19-2-1000.
\dagger Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge,
MA 02139 USA (blegat@mit.edu, ycy@mit.edu, parrilo@mit.edu).
2041

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

BENO\^IT LEGAT, CHENYANG YUAN, AND PABLO PARRILO

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

2042

where b(x) is a suitable polynomial basis of \BbbR [x]d . The constraint p(x) = b(x)\top  Xb(x)defines an affine subspace of the space of symmetric matrices, which can be expressedby matching the coefficients of p(x) with the corresponding coefficients of the polynomial b(x)\top  Xb(x).
Given the factorization X = U U \top  , where u\=1 , . . . , u\=r are the column vectors of U ,we have the explicit sum of squares decompositionp(x) =

(1.2)

r
\sum 

ui (x)2 ,i=1

where ui (x) = b(x)\top  u\=i . In other words, (1.2) is a formulation for the Burer--Monteiro
factorization of (1.1) independent of any particular basis. Instead of solving a SDP
to find ui (x), we apply a quadratic penalty to the equality constraint (1.2) to arriveat the following nonconvex objective:\bigm\| \bigm\| 2r\bigm\| \sum \bigm\| \bigm\| \bigm\| (1.3)
fp (u) = \bigm\| ui (x)2  -  p(x)\bigm\|  ,\bigm\| \bigm\| i=1\bigl[ \bigr] 

where u = u1 \cdot  \cdot  \cdot  ur is a vector of r degree-d polynomials and the norm is induced
by any inner product on polynomials of degree-2d. Then a degree-2d polynomial p(x)is a sum of r squares if and only if
min fp (u) = 0.

u\in \BbbR [x]rd

We say that u is a first-order critical point (FOCP) of fp (u) when \nabla fp (u) = 0,
where the derivatives are taken with respect to the variables in u. Since for every p we
can find spurious FOCPs (for example, taking u = 0), it is essential to consider secondorder necessary conditions. If u also satisfies \nabla 2 fp (u) \succeq  0, then it is a second-order
critical point (SOCP) of fp (u).
Every local minimum of a function is a SOCP, but the converse is not true when
the function is nonconvex.1 If u is not a SOCP, then we can produce a descentdirection using the gradient or Hessian. This leads to efficient first-order methods[20, 24] that converge to SOCPs. Thus if we can show that at every SOCP fp (u) = 0,
these algorithms will always converge to a global minimum. A recent line of work [8, 3]
has shown that for general SDPs under smoothed analysis or genericity conditions,when the rank of the factorization is above the Barvinok--Pataki bound (roughly thesquare root of the number of constraints), there are no spurious SOCPs. Moreover,the smoothed analysis or genericity conditions are necessary, as [3] constructed a SDP
where only a full-rank factorization can guarantee no spurious SOCPs.
In this paper we consider the setting of univariate polynomial optimization, which
is a class of problems with applications in signal processing, control [35, 17], and computing equilibria of polynomial games [33]. These optimization problems involving
nonnegative univariate polynomials can be transformed (i.e., by a bisection on the objective value) into feasibility problems for finding the sum of squares decompositionof a univariate polynomial. The main result of our paper shows that without any additional assumptions, the rank-2 quadratic-penalized Burer--Monteiro factorization of
the SDP describing the sum of squares decomposition (1.3) of a univariate polynomial
has no spurious SOCPs.
1 Consider, for example, f (x) = x3 at x = 0.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

LOW-RANK UNIVARIATE SUM OF SQUARES

2043

Theorem 1.1. For all nonnegative univariate polynomials p(x) \in  \BbbR [x]2d and any
r \geq  2, if u \in  \BbbR [x]rd satisfies \nabla fp (u) = 0 and \nabla 2 fp (u) \succeq  0, then fp (u) = 0.

In particular, the rank bound in our result matches the Pythagoras number for univariate polynomials [12, Example 2.13].2\surd In comparison, applying rank bounds forgeneral SDPs to this setting requires r \gtrsim  d (see section 2 for more details).
Theorem 1.1 is proved in section 4, by deriving a series of increasingly stronger
sufficient conditions ((C1), (C2), and (C3)) implying fp (u) = 0 for increasingly larger
classes of u = (u1 , u2 ), eventually proving the result for all u \in  \BbbR [x]2 . To illustrate
this, we first show that when r = 2 and u1 , u2 are coprime, \nabla fp (u) = 0 implies thatfp (u) = 0 (the precise statement and proof of this case are in subsection 4.1). Notethat in this simplified setting only the first-order gradient condition is needed. By
computing the gradient, \nabla fp (u) = 0 is equivalent to\bigl\langle \bigr\rangle \nabla fp (u)(v) = u1 v1 + u2 v2 , u21 + u22  -  p = 0
for all v = (v1 , v2 ) \in  \BbbR [x]2 . Since u1 , u2 are coprime, B\'ezout's identity (Lemma 3.3)
implies that we can find v\prime  = (v1\prime  , v2\prime  ) so thatu1 v1\prime  + u2 v2\prime  = u21 + u22  -  p,\bigm\| 2\bigm\| thus showing that fp (u) = \bigm\| u21 + u22  -  p\bigm\|  = 0. However, we cannot assume a priorithat u1 , u2 are coprime as we are only given p as the input. The main technicalcontribution of our proof is how to handle the more involved case when u1 , u2 share
a common factor.
We can also interpret our proof as a certificate. When we choose v\prime  satisfying(1.4), we obtain the identity(1.4)\nabla fp (u)(v\prime  ) = fp (u).
This implies that fp (u) = 0 when \nabla fp (u) = 0. In section 5 we generalize this example
to our full proof of Theorem 1.1, showing for all u and p how to find v\prime  and Q \succeq  0satisfying the following identity:\bigl\langle \bigr\rangle \nabla fp (u)(v\prime  ) + Q, \nabla 2 fp (u) =  - fp (u).

From this identity it is clear that if u is a SOCP, then fp (u) = 0. This compact formof our proof allows us to easily extend our result to other problems in section 6.
Since Theorem 1.1 holds for any inner product, we can choose one that enables
efficient computation of \nabla fp (u). When p is a degree-2d univariate polynomial, anequivalent way of ensuring the constraint p(x) = b(x)\top  Xb(x) in (1.1) is to write 2d + 1
xi ), where x\^0 , . . . , x\^d are distinct sample points. This
constraints p(\^xi ) = b(\^xi )\top  Xb(\^
formulation can be cast into the following least-squares objective:
2d+1\Bigr) 2\sum  \Bigl( \bigm\| \bigm\| 2
1\bigm\| U \top  b(\^(1.5)
xi )\bigm\| 2  -  p(\^xi ) .
min
fp (U ) =2d + 1 i=1
U \in \BbbR (2d+1)\times r
This is equivalent to choosing an inner product in (1.3) that evaluates the polynomial
on 2d+1 points. If we choose 2d+1 points on the complex unit circle, we can compute\nabla fp (U ) in O(d log d) time using the fast Fourier transform (FFT). In section 7, weshow that this method exhibits linear convergence experimentally using unconstrained
optimization algorithms such as L-BFGS and has near-linear scaling to million-degree
polynomials.
2 The Pythagoras number for \Sigma [x]2d is the smallest r such that all polynomials in \Sigma [x]2d can be
written as a sum of r squares of polynomials in \BbbR [x]d .

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy
22
where Diag U ⊤ Bk − p(xk ) is a diagonal matrix with U ⊤ Bk − p(xk ) as thek-th diagonal entry. Since matrix-vector multiplication by B is a equivalent to a
Discrete Fourier Transform, ∇fp (U ) can be computed in O(rd log d) time using the
FFT. Theorem 1.1 shows that spurious local minima do not exist when r ≥ 2, so we
can pick r to be a constant and obtain a near-linear iteration complexity. This is incontrast to other SDP-based algorithms and custom interior point methods for solving
2044problem, which
BENO\^IT
LEGAT,CHENYANG YUAN,
AND PABLO
PARRILO
thisrun
into computationaldifficulties
even when
2d = 10,000.
Table 11
Table
Time andand iterations
iterations toto convergence
convergence forfor sum
sumofofsquares
squaresdecomposition
decompositionofofrandom
randomnon-negative
nonnegativeTime
trigonometric polynomials.
polynomials. All
Allvalues
valuesarearemedian
medianofof5050runs
runs(with(withrange
rangebased
basedonon25-th
25thandand75-th
75th
trigonometricpercentile). Table 1
1(a)
fixes
rank
r and
(b) fixes
percentile).
fixes
the therank
r andandvaries
variesthethepolynomial
polynomial degree,degree whereas Table
2b thefixespolythe
nomial degree
andandvariesthe therankrankr. r.
polynomial
degreevariesDegreeTime (s)Iterations

r

Time

Iters

FFT Calls

2,000
10,00020,000100,000
200,000
1,000,000

2 (1 – 2)
6 (5 – 6)
9 (8 – 10)
53 (46 – 59)
160 (139 – 174)
1461 (1212 – 1532)

340 (306 – 384)
530 (497 – 592)
632 (587 – 695)
1126 (980 – 1248)
1375 (1212 – 1532)
2303 (1934 – 2437)

2
3
4
5
6
7

50
9
6
5
5
5

4124
896
530
446
396
374

20618
6272
4774
4900
5142
5618

(a) Varying degree, r = 4(b) Varying r, degree 2d = 10, 000

We
our algorithm
for finding
thecontributions
sum of squares
decomposition
1.1.implemented
Contributions.
In summary,
our mainin thispaper are: of
9trigonometricpolynomials
in
Julia
,
using
the
FFTW.jl[19]
packagefor FFTs forto
1. Proving that the quadratic penalty form of Burer--Monteiro factorization
compute univariate∇fp (U ) andthe
NLopt.jl[25]
packagetominimize
f
(U
)
using
a
first-orderppolynomial sum of squares decomposition has
no spurious SOCPs
algorithm(Theorem(L–BFGS).
WeOur
performed
the timingIntel
Xeon Platinum
1.1).
result holds
whereexperiments
the rank ofonthe
factorization
is at8260 processors,
allocating
at
least
r
+
1
cores
to
each
run,
using
polynomialsofleast 2, matching the Pythagoras number for univariate
polynomials.
This
is\surd 
degree-2dinranging
from
2,000
to
1,000,000.
The
testpolynomials
aregeneratedwithcontrast to previous work requiring rank r \gtrsim  d in addition to genericity
coefficients
drawn froma standard
normaldistribution,a constantcoefficientconditions
or smoothed
analysisfor general
SDPs, withor showingthat nospurious
added solocal
that minima
they allexist
haveina statisticalsmall positive
minimum
value.
Uisinitializedwith aproblems.
small 2.
randomvalue;
its
magnitude
depends
on
the
size
of
the
problem.
Thealgorithm
Developing a new framework for proving that there are no spurious SOCPs−7
is terminatedwhen the relative error
for eachentry
U is on theorder of 10
for a quadratic-penalized
factorized
SDP,
by of
constructing
a certificate(5.3).
Althoughusingr = the2 isfirstsufficient,
the results necessary
in Table conditions.
2b shows that= 4 minimizes
and second-order
Thisr certificate
reprethe totalsentation
computationalcost,
asmeasured
by
the
total
numberof
FFT
calls(by farhelps us extend our results to projection onto the sumof squares
the mostcone
expensive
operation)needed forconvergence.onInintervals
addition,(Corollary
since the 6.2)
matrix(Corollary6.1), certifying
nonnegativity
and
vector products
canbeeasilyparallelized
acrossmultiplethreads,
increasingr doessum of squares optimization.
not incur
a significant
if sufficientThus we choose
3. Showingthat per-iterationby choosing costa specialnormthreads(based areon used.
the evaluationof ther = 4 forpolynomial
our large-scale
experiments
in
Table
1.
Figure2plots
theconvergenceon points on the unit circle), the full gradient of the objectiverate
canof 20 instances,and wesee thattime
theyusingachievea linearconvergencerate. Thisisbe computedin cannear-linear
FFTs.
It enables
us to efficiently
scale
in contrast
togrid-based
methods
[41,
17]
which
scalessub-linearlyinaccuracy.
first-order methods to instances with millions of variables (Table 1a). This ispossible because our result (1.1) is independent of the penalty function.

9 The code and data required to reproduce the results in this section can be found in [28].

2. Background and related work. Let \BbbS n be the space of n \times  n symmetric matrices. Given Ai \in  \BbbS n , we consider the standard-form semidefinite feasibility
problem with variable X \in  \BbbS n :(SDP)\langle Ai , X\rangle  = bi ,X \succeq  0.

Nonconvex formulation. Burer and Monteiro [9] introduced the nonconvex reformulation X = U U \top  to enforce the semidefinite constraint, where U \in  \BbbR n\times r :\bigl\langle \bigr\rangle 
(NSDPr )Ai , U U \top  = bi .

This motivates the following least-squares formulation:\bigm\| \bigl\langle \bigr\rangle \sum  \bigm\| \bigm\|  Ai , U U \top   -  bi \bigm\| 2 .
min(SDPLSr )U \in \BbbR n\times riCopyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

LOW-RANK UNIVARIATE SUM OF SQUARES

2045

If in addition to the equality constraints in (SDP) one wishes to minimize the objective\langle C, X\rangle ,\bigl\langle the works\bigr\rangle  [10, 3, 14] formulate an augmented Lagrangian problem, where theterm \lambda  C, U U \top  is added to the objective of (SDPLSr ).
General SDP rank bounds. Burer and Monteiro subsequently showed in [10] thatwhen r \geq  n, there are no spurious SOCPs to (SDPLSr ). This result is in fact tightand [3] constructed an explicit instance where if r = n  -  1, one can find a SOCP thatis not a global minimum. Thus for general SDP feasibility, additional conditions on
the objective or analysis must be imposed. Then the rank bound can be improved tothe maximum rank of extreme points of \surd the section of the PSD cone with m affine
constraints. This maximum rank is O( m), also known as the Barvinok--Pataki
bound [2, 34]. In the same work, Burer and Monteiro[10] showed that when a linear\surd 
objective is added to (SDP) and (NSDPr ), if r \gtrsim  m, any local minimum of (NSDPr )is also a local minimum of (SDP) with an additional rank-r constraint. Then they
showed that such a local minimum is either an optimal extreme point or contained
within the relative interior of a face of the feasible set of (SDP), which is constantwith respect to the objective function.
Subsequent work [3] then showed that if C is generic enough, all local minimaof (NSDPr ) are global minima of (SDP) (see Cifuentes and Moitra [14] for morereferences). In summary, this line of work requires generic constraints, and in addition
either smoothness of the constraint set [7, 8] or smoothed
analysis [3, 14, 13]. In\surd 
addition, [40] showed that when r is smaller than m, SOCPs are not generically
optimal.
Structured SDPs. Problems such as matrix completion and matrix sensing canbe expressed as instances of (SDPLSr ). There has been a lot of recent interest in
studying the global landscape of matrix sensing problems [22, 4, 21]. A recent line ofwork [21, 22, 1] shows that for certain statistical problems aiming to recover a signal
in the form of a low-rank matrix corrupted by noise (where the SDP has a rank-1
solution in the noiseless setting), there are no spurious SOCPs when the noise level is
low enough. Similar results [21, 29, 39] can be obtained for matrix sensing, where a
low-rank matrix is reconstructed from linear measurements called sensing operators.
See [11] for a survey of these problems. In summary, for a wide range of statisticalproblems, local minima are also global minima. These results are either satisfied
with high probability or require that the sensing operators Ai satisfy the restrictedisometry property.
Sampling basis. The sampling or interpolation basis for sum of squares optimization is studied in [30] and [15]. Informally, they showed that if the sampled points
are ``generic"" enough, the problem expressed in the sampled basis is equivalent to
the original problem. This idea is also used for univariate polynomial optimization in[31, 26].
Univariate polynomials. Univariate/trigonometric polynomial optimization andtheir applications are studied in [41, 35, 17] and the references therein. The decomposition of a nonnegative trigonometric polynomial into a sum of squares is also known
as its spectral factorization [17, Theorem 1.1]. Previous methods for spectral factorization either require finding all n roots of the polynomial, solving linear systemsof order n, or using an approximate O(N log N ) FFT-based algorithm by samplingN \gg  n points [41, 17]. Design problems involving constraints on nonnegative trigonometric polynomials can be formulated as SDPs. Due to their special structure, [35]used FFTs to speed up per-iteration complexity for interior point methods solving
these SDPs to O(n3 ).

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

2046

BENO\^IT LEGAT, CHENYANG YUAN, AND PABLO PARRILO

The set of all X satisfying (1.1) is known as the Gram spectrahedron of p(x).
As the bounds developed for general SDPs depend on the rank of extreme points of
the Gram spectrahedra, one may wonder if this quantity can be tightly bounded (i.e.,
better than the Barvinok--Pataki bound) in the special case of univariate polynomials.
A recent work by Scheiderer [36] showed that this is not possible. If p(x) is a sufficiently general positive univariate polynomialof degree d, its Gram spectrahedron\surd 
has extreme points of all ranks up to O( d).
2.1. Notation. Let \BbbR [x]d be the space of univariate polynomials of degree at
most d. Let u(x) \in  \BbbR [x]rd be a vector of r polynomials where each ui (x) is a\sum polynomialrin \BbbR [x]d . Let \sigma  : \BbbR [x]rd \rightarrow  \BbbR [x]2d be the quadratic map defined by v(x) \mapsto \rightarrow  i=1 vi (x)2 ,1and \Sigma [x]2d := cone(\sigma (\BbbR [x]d )) \subseteq  \BbbR [x]2d be the cone of sum of squares univariate polynomials of degree-2d. A binary form is a homogeneous polynomial in two variables.
Let \BbbR [x]d be the space of binary forms of degree-d and \Sigma [x]2d \subseteq  \BbbR [x]2d be the spaceof sum of squares binary forms of degree-2d. \BbbR [x]d and \Sigma [x]2d are isomorphic to \BbbR [x]dand \Sigma [x]2d , respectively.
2.2. Univariate polynomials.
Any monic univariate polynomial p \in  \BbbR [x]d can\prod dbe uniquely factored as p(x) = i=1 (x  -  \alpha i ), where \alpha i \in  \BbbC  are the roots of p. Given
univariate polynomials p, g, and q, we define an equivalence relation p \equiv  q (mod g)
if there exists w \in  \BbbR [x] such that p = q + wg. We say that g is a divisor of p if p \equiv  0(mod g). In addition, if g is also a divisor of q, then we say that g is a common
divisor of p and q. Let gcd(p, q) be the greatest common divisor of p and q, which isthe common divisor with the highest degree. By the unique factorization of p and q,
gcd(p, q) is unique up to multiplication by a scalar. We say that p and q are coprime
if gcd(p, q) = 1.
\prod dAny binary form p \in  \BbbR [x]d can be factored as p(x1 , x2 ) = i=1 (\alpha i x1  -  \beta i x2 ),where (\alpha i , \beta i ) \in  \BbbC 2 . This factorization is unique up to multiplication of (\alpha i , \beta i ) by ascalar. The equivalence relation p \equiv  q (mod g) and gcd on binary forms are defined
analogously to those on univariate polynomials.
3. Preliminary results. Since the polynomials we are optimizing over have
fixed degrees, to better keep track of this degree we will work with homogeneouspolynomials (forms). In subsection 3.1 we derive expressions for the first- and secondorder necessary conditions ((3.3) and (3.4)). Next, in sections 3.2 and 3.3 we review
some results on binary forms and prove our main lemma, Lemma 3.7. Particularly
important is our decomposition of u in Proposition 3.4.
3.1. First- and second-order necessary conditions. First we derive expressions for the gradient and Hessian of fp (u). In addition to the binary forms we consider
in this paper, the derivations in this section also hold for general multivariate forms.
For any inner product on forms \langle \cdot , \cdot \rangle  : \BbbR [x]2d \times  \BbbR [x]2d \rightarrow  \BbbR  and its associated norm\| \cdot \|  : \BbbR [x]2d \rightarrow  \BbbR , the objective function is written as\bigm\| \bigm\| 2\bigm\|  r\bigm\| \bigm\| \sum \bigm\| 2\bigm\| fp (u(x)) = \bigm\| uj (x)  -  p(x)\bigm\| \bigm\|  .
\bigm\|  j=1
\bigm\| To find the gradient and Hessian of the objective, we compute the first- and secondorder terms of fp (u(x) + \epsilon v(x)) to obtain

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2047

LOW-RANK UNIVARIATE SUM OF SQUARES

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

(3.1)
(3.2)

1
\nabla u fp (u(x))(v(x)) =4
1 2\nabla  fp (u(x))(v(x), v(x)) =4 u\Biggl\langle  r
\sum 

j=1
\Biggl\langle  r\sum uj (x)vj (x),

r
\sum 
j=1

2

vj (x) ,

j=1

r
\sum 
j=1

2

\Biggr\rangle uj (x)  -  p(x) ,2\Biggr\rangle uj (x)  -  p(x)\bigm\| 2\bigm\| \bigm\| \bigm\| \sum \bigm\| \bigm\|  r\bigm\| uj (x)vj (x)\bigm\| + 2 \bigm\| \bigm\|  .
\bigm\| \bigm\|  j=1

Given a vector of polynomials u(x) \in  \BbbR [x]rd\bfone  , we define the linear map \scrA u(x) : \BbbR [x]rd\bftwo  \rightarrow \BbbR [x]d\bfone  +d\bftwo  asr\sum \scrA u(x) : v(x) \mapsto \rightarrow ui (x)vi (x).
i=1

For example, we can write \sigma (u) = \scrA u (u). When n = 2, \scrA u is up to a constant the
map induced by the Sylvester matrix [38]. If d1 = d2 , the determinant of \scrA u is up
to a constant the resultant of u1 and u2 ; it vanishes if and only if u1 and u2 share acommon divisor. Next we concisely define SOCPs using this new notation.

Definition 3.1. We say that u \in  \BbbR [x]rd is a SOCP of fp (u) if its gradient iszero and its Hessian is positive semidefinite. In other words, for all v \in  \BbbR [x]rd ,1(3.3)\nabla u fp (u)(v) = \langle \scrA u (v), \sigma (u)  -  p\rangle  = 0,
4
1 2
2
(3.4)
\nabla  fp (u)(v, v) = \langle \sigma  (v), \sigma (u)  -  p\rangle  + 2 \| \scrA u (v)\|  \geq  0.
4 u
Remark 3.2. The first-order condition (3.3) alone is insufficient to guarantee
global optimality, even when p is generic. For example, u = 0 is always a FOCP, but
is spurious if p \not = 0. Since we can always construct spurious FOCPs, even when p is
generic, we need to consider the second-order conditions.
3.2. Pairs of binary forms. In this section we present some results onpairs of binary forms that will be helpful for characterizing the sets3 Im(\scrA u ) andcone (\sigma  (ker(\scrA u ))) and proving Theorem 1.1 in section 4. From now on we assume
that r = 2 and u = (u1 , u2 ).
The following lemma is a restatement of B\'ezout's lemma for univariate polynomials using our notation. It states that any form in \BbbR [x]2d is in the image of the map\scrA u , as long as u1 and u2 are coprime. We provide a proof below for completeness.
Lemma 3.3. Given u = (u1 , u2 ) \in  \BbbR [x]2d\bfone  and d2 \geq  d1  -  1, consider the map \scrA u :\BbbR [x]2d\bftwo  \rightarrow  \BbbR [x]d\bfone  +d\bftwo  . Then u1 and u2 are coprime if and only if Im(\scrA u ) = \BbbR [x]d\bfone  +d\bftwo  .

Proof. For the ``if"" direction, when u1 and u2 are not coprime, they share acommon factor w with degree at least 1, and so does every form in Im(\scrA u ). Thus
Im(\scrA u ) is not equal to \BbbR [x]d\bfone  +d\bftwo  .
Next we prove the ``only if"" direction. Since \scrA u (v) = v1 u1 + v2 u2 , for every
v \in  ker(\scrA u ) we have
(3.5)

u1 v1 =  - u2 v2 .

3 For the more algebrically inclined reader, the sets Im(\scrA  ) and ker(\scrA  ) are the graded parts of
\bfu 
\bfu 

the ideal [16, Definition 1.4.1] and syzygy module [16, Definition 10.4.3] of u, respectively.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

2048

BENO\^IT LEGAT, CHENYANG YUAN, AND PABLO PARRILO

If d2 = d1  -  1, since u1 and u2 are coprime, by evaluating (3.5) on the roots of u1 andu2 we can conclude that v1 = v2 = 0 and dim(ker(\scrA u )) = 0. Otherwise if d2 \geq  d1 , this
implies that u1 is a divisor of v2 and u2 is a divisor of v1 . So there exists w1 , w2 \in \BbbR [x]d\bftwo   - d\bfone  such that v1 = w1 u2 , v2 = w2 u1 . Then (3.5) becomes (w1 + w2 )u1 u2 =0, implying that w2 =  - w1 . Thus ker(\scrA u ) = \{ (wu2 ,  - wu1 ) |  w \in  \BbbR [x]d\bftwo   - d\bfone  \}  anddim(ker(\scrA u )) = dim(\BbbR [x]d\bftwo   - d\bfone  ). In summary, d2 \geq  d1  - 1 implies that dim(ker(\scrA u )) =d2 + 1  -  d1 . Therefore, by the rank-nullity theorem,
dim(Im(\scrA u )) = 2 dim(\BbbR [x]d\bftwo  )  -  dim(ker(\scrA u )) = dim(\BbbR [x]d\bfone  +d\bftwo  ).

Since Im(\scrA u ) \subseteq  \BbbR [x]d\bfone  +d\bftwo  and these two sets have the same dimensions, they must
be equal.
In particular, Lemma 3.3 motivates the decomposition u1 = u\prime 1 g\^ and u2 = u\prime 2 g,\^
where u\prime 1 and u\prime 2 are coprime and g\^ = gcd(u1 , u2 ). Indeed when g\^ = 1 we can apply
the sufficient condition (C1) in subsection 4.1 to show that u is not a SOCP. When
gcd(\^
g, \sigma (u\prime  )) = 1 we can apply (C2) in subsection 4.2. Otherwise we need to partition
the roots of g\^ = gh by whether each root is also a root of \sigma (u\prime  ), then apply (C3) in
subsection 4.3.
Proposition 3.4. Given u = (u1 , u2 ) \in  \BbbR [x]2d , we can always find g \in  \BbbR [x]m ,h \in  \BbbR [x]k , and u\prime  = (u\prime 1 , u\prime 2 ) \in  \BbbR [x]2d - m - k so that
(u1 , u2 ) = (u\prime 1 gh, u\prime 2 gh),gcd(u1 , u2 ) = gh,
gcd(u\prime 1 , u\prime 2 ) = 1,2

2

gcd(\sigma (u\prime  ), g) = gcd(u\prime 1 + u\prime 2 , g) = 1,
r is a (possibly complex) root of h \Rightarrow  r is a root of \sigma (u\prime  ).
Moreover, this decomposition is unique up to multiplication by constants.
Proof. Let g\^ = gcd(u1 , u2 ) so that u\prime 1 = u1 /\^g and u\prime 2 = u2 /\^g. By partitioning theroots of g\^ we can decompose g\^ = gh, where g has no common roots with \sigma (u\prime  ) andevery root of h is also a root of \sigma (u\prime  ). The uniqueness of this decomposition follows
from the unique factorization theorem for binary forms.
We demonstrate this decomposition with an example.
Example 3.5. Let u1 (x1 , x2 ) = (x21 + x22 )2 (2x21 + x22 )x21 and u2 (x1 , x2 ) = (x21 +2 2x2 ) (2x21 +x22 )x1 x2 . Then the decomposition in Proposition 3.4 gives u\prime 1 = x1 , u\prime 2 = x2 ,g = x1 (2x21 + x22 ), and h = (x21 + x22 )2 .
The following observation about the roots of \sigma (u\prime  ) and h is useful in our proofs.
Proposition 3.6. In the decomposition of Proposition 3.4, both \sigma (u\prime  ) and h haveno real roots and deg(h) is even.
Proof. If \sigma (u\prime  ) has a real root x,\^ then u\prime 1 (\^x)2 + u\prime 2 (\^x)2 = 0. Thus x\^ is a root of u\prime 1
and u\prime 2 , contradicting the fact that gcd(u\prime 1 , u\prime 2 ) = 1. Thus every root of h is complex,
and h must have even degree.
3.3. Main lemma. In our proof of Theorem 1.1 we will use the following main
result, which may be of independent interest.
Lemma 3.7. Given binary forms g \in  \BbbR [x]m , q \in  \Sigma [x]2d - 2m , and p \in  \Sigma [x]2d , if g
and q are coprime, then there exists a sum of squares binary form s \in  \Sigma [x]2m suchthat

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

LOW-RANK UNIVARIATE SUM OF SQUARES

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

p \equiv  sq

2049(mod g).

The main ingredient of the proof of Lemma 3.7 is a result stating that any univariate
polynomial a(x) strictly positive on the real zeros of g(x) can be written as a single
square4 modulo g(x).
Proposition 3.8. Let g(x) and a(x) be coprime univariate polynomials wheredeg(g) = m. If a(x) > 0 for all \{ x \in  \BbbR  |  g(x) = 0\} , then there exists a polynomial
t \in  \BbbR [x]m such thata \equiv  t2(mod g).

This result is related to Schm\"udgen's certificate [37], which states that if a polynomialis strictly positive on a compact semialgebraic set, then it has a Positivstellensatz
certificate in terms of the equations describing the set.
\sqrt{}  We prove Proposition 3.8
using Hermite interpolation on the series expansion of a(x) around the roots of g.

Proof of Proposition 3.8. \sum Let ri be the roots (possibly complex) of g(x), eachwith multiplicity
n
,
so
that
i
i ni = m. Consider the Taylor series expansion of\sqrt{} f (x) = a(x) centered at ri . Since a and g do not share any common roots asthey are coprime, this Taylor series is well defined around any root of g. Let thepolynomials \gamma i (x) be the first ni terms of the Taylor expansion of f (x) centered atri . The polynomials \gamma i have real coefficients if ri is real, and if ri and rj are apair of conjugate roots, \gamma i = \gamma \=j . We can then use the Chinese Remainder Theorem[18, section 7.6] to construct the unique polynomial t(x) with real coefficients anddeg(t) < m such thatfor all i,t(x) \equiv  \gamma i (x)(mod (x  -  ri )ni ).

By construction, for all roots ri of g and any k = 0, . . . , ni  -  1, we havedkdkdkf (ri ) = k \gamma i (ri ) = k t(ri ).
k
dx
dx
dx
For each root ri , we have\sqrt{} anda(ri ) = f (ri ) = \gamma i (ri ) = t(ri )dddda(ri ) = 2f (ri ) f (ri ) = 2t(ri ) t(ri ) =t(ri )2 .
dx
dx
dx
dx
k

k

d
d
2
By induction we get dx
k a(ri ) = dxk t(ri ) for k = 0, . . . , ni  -  1. This is a generalizationof Hermite interpolation for a variable number of consecutive derivatives at eachpoint [23, section 17.6].5 Since a(x) and t(x)2 match at all the roots of g (including
derivatives up to the multiplicity of the root), we have shown that a \equiv  t2 (mod g).

Then we prove the affine version of Lemma 3.7.

4 The number of squares is not important in our proof of Lemma 3.7; we only need the property
that a(x) can be written as a sum of squares modulo g(x).
5 This is referred to as Birkhoff interpolation in [23], and the existence of a unique interpolating
polynomial crucially depends on the use of consecutive derivatives.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

2050

BENO\^IT LEGAT, CHENYANG YUAN, AND PABLO PARRILO

Lemma 3.9. Let g, p, and q be univariate polynomials where deg(g) = m, deg(p) =2d, and deg(q) = 2d - 2m, p and q are sum of squares, and g and q are coprime. Then
there exists a sum of squares polynomial s \in  \Sigma [x]2m such thatp \equiv  sq(mod g).

Proof. Since q is coprime with g, Lemma 3.3 (after reducing q modulo g) guarantees that there exists a polynomial a \in  \BbbR [x]m such that
(3.6)

aq \equiv  1(mod g).

We have q(x) > 0 for all real roots x of g, since q is nonnegative and coprime withg. Thus a(x) > 0 for all real roots x of g, by evaluation of (3.6) at these roots.
Since a(x)q(x) = 1 for all roots x of g, a is also coprime with g. Then we can apply
Proposition 3.8 to find t \in  \BbbR [x]m so that a \equiv  t2 (mod g). Multiplying both sides of(3.6) by p, we get
p \equiv  t2 pq(mod g).

Since t2 p is a sum of squares, we can reduce each squared polynomial modulo g to
get s \in  \Sigma [x]2m .
Finally we prove Lemma 3.7, which is the projective version of Lemma 3.9.

Proof of Lemma 3.7. We first apply a linear change of coordinates so that (0, 1)
is not a root of g, p, or q. Then let g \prime  (x) = g(x, 1), p\prime  (x) = p(x, 1), and q \prime  (x) = q(x, 1).
Since this dehomogenization procedure preserves the degree of g, p, and q,6 we canapply Lemma 3.9 to find polynomials s\prime  \in  \Sigma [x]2m and t\prime  \in  \BbbR [x]2d - m so thatp\prime  = s\prime  q \prime  + t\prime  g \prime  .
\prime We can then homogenize by letting s(x1 , x2 ) = x2m
2 s (x1 /x2 ) and t(x1 , x2 ) =2d - m \prime x2
t (x1 /x2 ). Thus s is also a sum of squares andp = sq + tg.
4. Main theorem and proof. In this section we prove Theorem 1.1, whichstates that for univariate polynomials, a rank-2 decomposition has no spurious secondorder critical points. Using the decomposition in Proposition 3.4, we first prove simplified versions of Theorem 1.1 in sections 4.1 and 4.2, before proving the full version
in subsection 4.3.
4.1. Coprime case: \bfitg  = 1, \bfith  = 1. This is the case explained in the introduction. In the decomposition of Proposition 3.4, g = h = 1 implies that u1 and u2
are coprime. This happens generically and implies that for a fixed p, the gradientcondition (3.3) is sufficient for almost all u.
Proposition 4.1. Suppose u \in  \BbbR [x]2d and p \in  \Sigma [x]2d satisfies \nabla fp (u) = 0. If(C1)p \in  Im(\scrA u ),then we have fp (u) = 0.
6 If the degree of g is not preserved after dehomogenization, the degree of t\prime  after applying
Lemma 3.9 could be larger than 2d  -  m. For example, if d = m = 2, g = x1 x2 , p = (2x21 + x22 )x22 , andq = 1, we get that s\prime  = (x2 + 1)2 and t\prime  =  - x3 after dehomogenizing and applying Lemma 3.9. Thisissue will not occur if the dehomogenization is degree-preserving.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

LOW-RANK UNIVARIATE SUM OF SQUARES

2051

Proof. Since p \in  Im(\scrA u ), we can find v \in  \BbbR [x]2d so that \scrA u (v) = \sigma (u)  -  p. Eval2
uating the gradient condition (3.3) at v, we conclude that fp (u) = \| \sigma (u)  -  p\|  = 0.

Since Lemma 3.3 implies that Im(\scrA u ) = \BbbR [x]2d if and only if u1 and u2 are coprime,
we have shown that when g = h = 1, we always have p \in  Im(\scrA u ) and there are no
spurious FOCPs and SOCPs.

4.2. Special case: \bfith  = 1. When u1 and u2 are not coprime, \sigma (u)  -  p might
not be in Im(\scrA u ) and we cannot use the argument in Proposition 4.1. Thus we need
to use make use of the Hessian condition (3.4).
Proposition 4.2. Suppose u \in  \BbbR [x]2d and p \in  \Sigma [x]2d satisfies \nabla fp (u) = 0 and\nabla  fp (u) \succeq  0. If
2p \in  Im(\scrA u ) + cone (\sigma  (ker(\scrA u ))) ,(C2)
then we have fp (u) = 0.

This means that if for all u we can decompose p = q +r, where q \in  Im(\scrA u ) and r \in cone (\sigma  (ker(\scrA u ))), then fp (u) has no spurious SOCPs. In particular, similar to how
Im(\scrA u ) is related to the gradient condition (3.3) in Proposition 4.1, cone (\sigma  (ker(\scrA u )))is related to the Hessian condition (3.4). The following result states that (C2) issatisfied if h = 1.
Lemma 4.3. Given u \in  \BbbR [x]2d , if in the decomposition of Proposition 3.4 we have
h = 1, then for every p \in  \Sigma [x]2d ,p \in  Im(\scrA u ) + cone (\sigma  (ker(\scrA u ))) .
Proof. We want to show that any p(x) \in  \Sigma [x]2d can be written as the sum of polynomials in Im(\scrA u ) and \sigma (ker(\scrA u )). Therefore it is useful to have a characterizationof these sets. Lemma 3.3 tells us that
Im(\scrA u ) = \{ \scrA u\prime  (v)g |  v \in  \BbbR [x]d \} 

= \{ wg |  w \in  \BbbR [x]2d - m \}  .

Since for all t \in  \BbbR [x]m we have ( - tu\prime 2 , tu\prime 1 ) \in  ker(\scrA u ),\bigl\{  2\bigr\} t \sigma (u\prime  ) |  t \in  \BbbR [x]m \subseteq  \sigma (ker(\scrA u )),(4.1)\{ s\sigma (u\prime  ) |  s \in  \Sigma [x]2m \}  \subseteq  cone(\sigma (ker(\scrA u ))).

Since \sigma (u\prime  ) is coprime with g by assuming h = 1, we can apply Lemma 3.7 to showthat there exists w \in  \BbbR [x]2d - m and s \in  \Sigma [x]2m such that p = s\sigma (u\prime  ) + wg.
Finally we prove Proposition 4.2.

Proof of Proposition 4.2. The condition (C2) implies that there exist v \in \BbbR [x]2d , w(i) \in  ker(\scrA u ) such that\sum p = \scrA u (v) +\sigma (w(i) ).
i

Since \nabla fp (u) = 0, (3.3) implies that
(4.2)

\langle \scrA u (v), \sigma (u)  -  p\rangle  = 0.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

2052

BENO\^IT LEGAT, CHENYANG YUAN, AND PABLO PARRILO

Since \nabla 2 fp (u) \succeq  0 and w(i) \in  ker(\scrA u ), (3.4) implies that
\Bigl\langle 
\Bigr\rangle (4.3)\sigma (w(i) ), \sigma (u)  -  p \geq  0.
Combining (4.2) and (4.3) gives\langle p, \sigma (u)  -  p\rangle  \geq  0.

(4.4)
Since \nabla fp (u) = 0 implies that\langle \scrA u (u), \sigma (u)  -  p\rangle  = \langle \sigma  (u), \sigma (u)  -  p\rangle  = 0,
we have2

fp (u) = \| \sigma (u)  -  p\|  = \langle \sigma  (u)  -  p, \sigma (u)  -  p\rangle  =  -  \langle p, \sigma (u)  -  p\rangle  .
This together with (4.4) implies that fp (u) \leq  0. However fp (u) is always nonnegative,
and thus it must be 0.
4.3. General case. Lemma 4.3 alone is insufficient to prove Theorem 1.1. It
is possible for g\^ = gcd(u1 , u2 ) to share complex roots with \sigma (u\prime  ) (recall from Proposition 3.6 that all roots of \sigma (u\prime  ) are complex), as seen in Example 3.5. Hence theargument in the proof of Lemma 4.3 fails as g\^ is not coprime with \sigma (u\prime  ). To getaround this issue, we will derive the sufficient condition (C3) in Proposition 4.4, astronger version of (C2), by carefully examining the Hessian condition (3.4). Roughly
speaking, Proposition 4.4 shows that we can replace every root of h (which must becomplex) with any real root.7 Since \sigma (u\prime  ) has no real roots, gx\^ k1 /h is now coprime\prime with \sigma (u ), and we can then complete the proof by following the argument in theprevious section.
Proposition 4.4. Suppose u \in  \BbbR [x]2d and p \in  \Sigma [x]2d satisfies \nabla fp (u) = 0
and \nabla 2 fp (u) \succeq  0, with the decomposition in Proposition 3.4, where k = deg(h) anduxk1 /h = (u\prime 1 gxk1 , u\prime 2 gxk1 ). If\Bigl( \Bigr) (C3)
p \in  Im \scrA uxk1 /h + cone (\Sigma  (ker(\scrA u ))) ,then fp (u) = 0.

Proof. We first prove that if r \in  \BbbR [x]\ell  is a common divisor of \sigma (u\prime  ) and g\^ =gcd(u1 , u2 ), then\bigl\langle \bigr\rangle 
(4.5)\scrA u (b)x\ell 1 /r, \sigma (u)  -  p = 0 for all b = (b1 , b2 ) \in  \BbbR [x]2d .

Given any b1 , b2 \in  \BbbR [x]d and \eta  \in  \BbbR , let v1 = \eta x\ell 1 u2 /r + b2 and v2 =  - \eta x\ell 1 u1 /r  -  b1 .
We have

(4.6)
(4.7)

\scrA u (v) = u1 (\eta x\ell 1 u2 /r + b2 )  -  u2 (\eta x\ell 1 u1 /r + b1 ) = u1 b2  -  u2 b1 ,

2
2
2
\ell 
2
2
\sigma (v) = \eta  2 x2\ell 1 (u1 + u2 )/r + 2\eta x1 (b1 u1 + b2 u2 )/r + (b1 + b2 ).

22
22\ell 
\prime  2 2Since r is a divisor of both \sigma (u\prime  ) and g,\^ x2\ell g /r is a multiple
1 (u1 + u2 )/r = x1 \sigma (u )\^2\ell  2
2
2of g.
\^ Thus x1 (u1 + u2 )/r \in  Im(\scrA u ) and we have\bigl\langle  2 2\ell  2\bigr\rangle \eta  x1 (u1 + u22 )/r2 , \sigma (u)  -  p = 0.
7 Without loss of generality we choose this real root to be x .
1

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

LOW-RANK UNIVARIATE SUM OF SQUARES

2053

Therefore, the Hessian condition (3.4) implies that for all \eta  \in  \BbbR ,\bigl\langle \bigr\rangle  \bigl\langle \bigr\rangle 2(4.8) 2\eta  (b1 u1 + b2 u2 )x\ell 1 /r, \sigma (u)  -  p + b21 + b22 , \sigma (u)  -  p + 2 \| u1 b2  -  u2 b1 \|  \geq  0.

This implies the identity (4.5); otherwise there exists \eta  such that (4.8) is negative.
\prod k/2
Since \sigma (u\prime  ) and h have no real roots (Proposition 3.6), we can write h = i=1 ri ,where each ri \in  \BbbR [x]2 is a quadratic form corresponding to the product of a pair ofcomplex roots. We first apply the same argument from above to show that\bigl\langle \bigr\rangle 
(4.9)\scrA u (b)x21 /r1 , \sigma (u)  -  p = 0 for all b \in  \BbbR [x]2d .
Next we show that (4.9) implies that\bigl\langle \bigr\rangle 
\scrA u (b)x41 /(r1 r2 ), \sigma (u)  -  p = 0 for all b \in  \BbbR [x]2d .
(4.10)

Similar to before, let r = r1 r2 so we have the identities (4.6) and (4.7) as before.
\prime \^ g\^\prime  22
8 \sigma (u ) g
Since r2 is a divisor of both \sigma (u\prime  ) and g/r\^ 1 , x81 \sigma (ug /(r\Bigl(  )\^
\Bigr)  1 r2 ) = x1 r2 r1 r2 r1 is amultiple of g/r\^ 1 . Thus x81 \sigma (u\prime  )\^g 2 /(r1 r2 )2 \in  Im \scrA ux21 /r1 and we then use (4.9) toshow (4.10).
Thus by iteratively applying the previous arguments,8 we show that for every
1 \leq  k \prime  \leq  k/2 and b \in  \BbbR [x]2d ,\Biggl\langle \prime \prime \scrA u (b)x2k
1 /k\prod 

i=1

\Biggr\rangle ri , \sigma (u)  -  p

= 0.

\prod k\prime This is because each ri is a divisor of \sigma (u\prime  ) and i=1 ri divides g.
\^ From here we canfinish our proof by following the same steps as in the proof of Proposition 4.2.

With Proposition 4.4 we can prove Theorem 1.1, by showing that every p \in  \Sigma [x]2d
has the required decomposition.
\bigl\langle \bigr\rangle 
Proof of Theorem 1.1. Since \scrA u\prime \bigl\langle (b)gxk1 , \sigma (u)  -  \bigr\rangle p = 0 for all b \in  \BbbR [x]2d and u\prime 1 , u\prime 2
are coprime, Lemma 3.3 implies that wgxk1 , \sigma (u)  -  p = 0 for all w \in  \BbbR [x]. Since \sigma (u\prime  )
has no real roots (Proposition 3.6), it is coprime with xk1 . As \sigma (u\prime  ) is coprime with g,
it is also coprime with gxk1 . Thus Lemma 3.7 tells us that there exists a sum of squares
polynomial s such that p \equiv  s\sigma (u\prime  ) (mod gxk1 ). Since s\sigma (u\prime  ) \in  cone(\sigma (ker(\scrA u ))) by(4.1), we are done.
5. Geometric interpretation and certificates. In this section, we provide
a geometric interpretation of our proof of Theorem 1.1, which allows us to turn the
proof into a certificate. In order to prove that there are no spurious second-order2
critical points when minimizing fp (u) = \| \sigma (u)  -  p\|  , we have to show that for all
r2
u \in  \BbbR [x] and for all p \in  \Sigma [x], \nabla fp (u) = 0 and \nabla  fp (u) \succeq  0 imply that fp (u) = 0
and p = \sigma (u). One way to tackle this problem is to fix p then characterize the setof u satisfying the second-order critical point conditions. This is the approach taken
by [3] and related works, where they used an argument based on the dimension of
the subspace generated by the constraints of the SDP. However, the SOCP conditions
8 The argument here is subtle because although every root of h is a root of \sigma (u\prime  ), a root may havehigher multiplicity in h than in \sigma (u\prime  ). For example, it is possible that h = (x21 + x22 )2 but \sigma (u\prime  ) =x21 + x22 . In this case, to obtain (4.5) we need to iteratively ``peel off"" the factors r1 = r2 = x21 + x22 ,by first proving (4.9) and then proving (4.10).

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

BENO\^IT LEGAT, CHENYANG YUAN, AND PABLO PARRILO

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

2054



p ∈ Σ[x] | ∇2 fp (u)  0

p = σ(u){p ∈ R[x] | ∇fp (u) = 0}
Fig. 1. The geometric interpretation.

are nonconvex in u. In order to do better than a dimension-counting argument, ourproof takes a different approach. If we fix u, the set of all p satisfying the gradientcondition (3.3) is an affine subspace, whereas the set of all p \in  \Sigma [x] satisfying the
Hessian condition (3.4) is a convex semidefinite-representable set. We need to showthat these two sets intersect at only one point, p = \sigma (u) (see Figure 1).
Our proof can be interpreted as constructing a certificate to show that these two
sets only intersect at one point. This is true if and only if the following optimization
problem has a zero optimal objective value:\bigl\langle \bigr\rangle 
2
(5.1)
max
min r \| \sigma (u)  -  p\|  + \nabla fp (u)(\bfitlambda ) + Q, \nabla 2 fp (u) .
p\in \Sigma [x] Q\succeq 0, \bfitlambda \in \BbbR [x]Expanding the gradient and Hessian, we getwhere Q =
(5.2)

\sum 

\bigl\langle \nabla fp (u)(\bfitlambda ) = \langle \scrA u (\bfitlambda ), \sigma (u)  -  p\rangle  ,\bigm\| \bigm\| 2\Bigr\rangle \bigr\rangle  \sum  \Bigl\langle \bigm\| \bigm\| Q, \nabla 2 fp (u) =\sigma (v(i) ), \sigma (u)  -  p + 2 \bigm\| \scrA u (v(i) )\bigm\|  ,ivi(i) (i) \top v. If for every p \in  \Sigma [x] we can find \bfitlambda  and Q such that\bigl\langle \bigr\rangle 2\nabla fp (u)(\bfitlambda ) + Q, \nabla 2 fp (u) =  -  \| \sigma (u)  -  p\|  ,then the objective of (5.1) is at most 0 and cannot be positive, showing that p = \sigma (u)is the only point satisfying the gradient and Hessian conditions. \bigl\langle Since \scrA u (u)\bigr\rangle  =\sigma (u), this is equivalent to finding \bfitlambda  and Q such that \nabla fp (u)(\bfitlambda ) + Q, \nabla 2 fp (u) =\langle p, \sigma (u)  -  p\rangle .
5.1. Warmup. As a warmup, we construct such a certificate if h = 1 in thedecomposition of u in Proposition 3.4. Recall that in this case g = gcd(u1 , u2 ), u1 =gu\prime 1 , u2 = gu\prime 2 , and \sigma (u\prime  ) is coprime with g \in  \BbbR [x]m . Therefore, by Lemma 3.7, there
exists s \in  \Sigma [x]2m such that p \equiv  s\sigma (u\prime  ) (mod g). Let\biggr] \biggl[  \prime  2
 - u\prime 1 u\prime 2
u2
.
Q=s
2
u\prime 1
 - u\prime 1 u\prime 2
As both \sigma (u) and p  -  s\sigma (u\prime  ) are divisible by g, Lemma 3.3 implies that there exists\bfitlambda  such that:\scrA u (\bfitlambda ) =  - \sigma (u) + p  -  s\sigma (u\prime  ).

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2055

LOW-RANK UNIVARIATE SUM OF SQUARES

These values of \bfitlambda  and Q give

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

2\nabla fp (u)(\bfitlambda ) =  -  \| \sigma (u)  -  p\|   -  \langle s\sigma (u\prime  ), \sigma (u)  -  p\rangle  ,\bigl\langle \bigr\rangle 
Q, \nabla 2 fp (u) = \langle s\sigma (u\prime  ), \sigma (u)  -  p\rangle  ,and hence taking the sum we have the identity (5.2).

5.2. Certificate. Now we can present the proof of Theorem 1.1 in the form ofa certificate. First we decompose u \in  \BbbR [x]2d as in Proposition 3.4. Since g is coprime
with \sigma (u\prime  ) and \sigma (u\prime  ) has no real roots, gxk1 is also coprime with \sigma (u\prime  ). Then by
Lemma 3.7, there exists s \in  \Sigma [x]2(m+k) such that p \equiv  s\sigma (u\prime  ) (mod gxk1 ). Next weapply Lemma 3.3 to find b0 \in  \BbbR [x]2d so thatxk
2 1 \scrA u (b0 ) = 2gxk1 \scrA u\prime  (b0 ) = p  -  s\sigma (u\prime  ).
h\prod k/2
As in the proof of Proposition 4.4, we write h = i=1 ri . For every 1 \leq  j \leq  k/2, since
rj divides \sigma (u\prime  ), by Lemma 3.3 there exists bj \in  \BbbR [x]2d so that
2gxk - 2j\scrA u\prime  (bj )1j\prod 

i=1

2k - 4(j - 1)
ri =  - g 2 x1
\sigma (u\prime  )Given any a = (a1 , a2 ) \in  \BbbR [x]2d , we define \=a := (a2 ,  - a1 ).
jfor every 0 \leq  j \leq  k/2 let \eta j = \eta  3 and
3/2

vj = \eta j gxk - 2ju\= \prime 1

j\prod 

j - 1
\prod 

ri2 .

i=1

Given a parameter \eta  \in  \BbbR , - 1/2 \= jri + \eta j

b .

i=1

Then define
k/2\prime  \prime  \top Q = s\=uu\=

1 \sum  j j \top v v ,+\eta  j=0

\bfitlambda  =  - (1 + \eta   - 1 \eta k/2+1 )u.
jj\= ) = \sigma (bj ), \scrA u\=\prime  (b\= ) = \scrA u\prime  (bj ), and \eta j +1 = \eta  3 ,Since \scrA u (\=u\prime  ) = 0, \sigma (\=u\prime  ) = \sigma (u\prime  ), \sigma (bjwe have\Biggr) \Biggl( 
k/2
k/2
j
j
\prod 
\prod 
1 \sum  3 2 2k - 4j
1 \sum k - 2jjj
 - 1
j\prime 2\sigma (v ) =\eta  g x1
\sigma (u )ri + 2\eta j gx1 \scrA u\prime  (b )ri + \eta j \sigma (b )\eta  j=0
\eta  j=0 j
i=1
i=1\prime = p  -  s\sigma (u ) + \eta  - 1\eta k/2+1 \sigma (u) + \eta 

 - 1

k/2
\sum 

\eta j - 1 \sigma (bj ),j=0

 - 1/2\= j ),\scrA u (v ) = \eta j\scrA u (bj\Biggl\langle 
\Biggr\rangle 
k/2
\sum 
\bigl\langle \bigr\rangle 
j
 - 1
2
 - 1
 - 1
Q, \nabla  fp (u) = p + \eta  \eta k/2+1 \sigma (u) + \eta \eta j \sigma (b ), \sigma (u)  -  p
j=0

\bigm\| \bigm\| 2\sum \bigm\| \= j )\bigm\| +2\eta j - 1 \eta   - 1 \bigm\| \scrA u (b\bigm\|  ,
k/2

j=0

\nabla fp (u)(\bfitlambda ) =  - (1 + \eta   - 1 \eta k/2+1 ) \langle \sigma  (u), \sigma (u)  -  p\rangle  .

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

2056

BENO\^IT LEGAT, CHENYANG YUAN, AND PABLO PARRILO

So we have proven the identity\bigl\langle \bigr\rangle 2(5.3) \nabla fp (u)(\bfitlambda ) + Q, \nabla 2 fp (u) =  -  \| \sigma (u)  -  p\| \biggl( k/2\bigm\| 2 \biggr) \bigm\| \sum \bigr\rangle 1 \bigl\langle \bigm\| \= j )\bigm\| +\sigma (bj ), \sigma (u)  -  p + 2 \bigm\| \scrA u (b\bigm\|  .
\eta \eta j
j=0This implies that for every \eta  > 0 and every u that satisfies \nabla fp (u) = 0 and\nabla 2 fp (u) \succeq  0,2\| \sigma (u)  -  p\|  \leq 

k/2
\sum 
j=0

j

\eta   - (3 +1)\biggl( \bigm\| 2 \biggr) \bigm\| \bigl\langle \bigr\rangle \bigm\| \= j )\bigm\| \sigma (bj ), \sigma (u)  -  p + 2 \bigm\| \scrA u (b\bigm\|  .

Since bj does not depend on \eta , we can make the right hand side arbitrarily small bytaking the limit \eta  \rightarrow  \infty . Thus we can conclude that \| \sigma (u)  -  p\|  = 0.
6. Extensions and generalizations. The certificate interpretation discussed
in the previous section allows us to generalize Theorem 1.1 to other settings, such as
projecting onto the sum of squares cone, certifying nonnegativity on intervals, andimposing linear constraints on coefficients of univariate sum of squares polynomials.
6.1. Projection onto the sum of squares cone. A natural question to consider is what happens to the optimization landscape of fp (u) when p cannot be expressed as a sum of squares. In this case the objective fp (u) can never be zero, but
we show that all SOCPs have the same objective value, which is the projection of p
to the sum of squares cone.
Corollary 6.1. For all u \in  \BbbR [x]2d where \nabla fp (u) = 0 and \nabla 2 fp (u) \succeq  0, \sigma (u) isthe projection of p to the sum of squares cone with respect to the inner product used22
to define fp . In other words, fp (u) = \| \sigma (u)  -  p\|  \leq  \| q  -  p\|  for all q \in  \Sigma [x]2d .

Proof. Corollary 6.1 can be proved by a simple modification of the certificate(5.3). Although p is no longer a sum of squares, we can use (5.3) to show that for all
q \in  \Sigma [x]2d ,\langle \sigma  (u)  -  q, \sigma (u)  -  p\rangle  \leq  0.
This is exactly the variational characterization of projection onto the convex cone
\Sigma [x]2d .

6.2. Certifying nonnegativity on intervals. Suppose we wish to\bigcup mcertify thata univariate polynomial p(x) is nonnegative in a union of intervals I = i=1 Ii where
Ii = \{ x \in  \BbbR  |  \alpha i \leq  x \leq  \beta i \} . This can be accomplished by finding a decompositionp(x) =m\sum ai (x)qi (x),iwhere ai (x) are fixed polynomials depending on the intervals Ii and qi (x) are sum ofsquares polynomials (see, e.g., [5, Theorem 3.72]). This objective can \sum also be writtenr
as a nonconvex optimization problem by the decomposition qi (x) = j=1 uij (x)2 =\sigma (ui ). If we lets(u)(x) =m\sum ai (x)\sigma (ui ),i=1

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

LOW-RANK UNIVARIATE SUM OF SQUARES

2057

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

then the objective fpI (u) and its gradient and Hessian can be written as\bigm\| m\bigm\| \sum \bigm\| 2\bigm\| \bigm\| 2
ai \sigma (ui )  -  p\bigm\|  = \| s(u)  -  p\|  ,\bigm\| \bigm\| \Biggl\langle i=1\Biggr\rangle 
m
\sum 
I
\nabla fp (u)(v) =ai \scrA ui (vi ), s(u)  -  p ,\bigm\| fpI (u) = \bigm\| i=1\nabla 2 fpI (u)(v, v) =\Biggl\langle  m
\sum 
i=1

ai \sigma (vi ), s(u)  -  p

\Biggr\rangle \bigm\| \bigm\| 2m\bigm\| \sum \bigm\| \bigm\| \bigm\| + 2 \bigm\| ai \scrA ui (vi )\bigm\|  .
\bigm\| \bigm\| i=1\sum mCorollary 6.2. Suppose r \geq  2 and we are given p = i=1 ai qi \in  \BbbR [x]2d+k ,where ai \in  \BbbR [x]k , qi \in  \Sigma [x]2d . For all u \in  \BbbR [x]m\times r
such that \nabla fpI (u) = 0 anddII\nabla fp (u) \succeq  0, fp (u) = 0.

Proof. We can prove this by constructing a certificate of the form (5.3). For each
i we can choose vj = 0 for all j \not = i, then follow the reasoning in subsection 5.2 to find\bfitlambda i and Qi such that for all \eta i > 0,
\bigl\langle \bigr\rangle (6.1)\nabla fpI (u)(\bfitlambda i ) + Qi , \nabla 2 fpI (u) = \langle ai qi , s(u)  -  p\rangle  + Ci ,where Ci is a value that can be made arbitrarily small by taking a limit. We thensum (6.1) for all i, along with the equality \nabla fpI (u)( - u) =  -  \langle s(u), s(u)  -  p\rangle  to get
\sum 
2
2
\| s(u)  -  p\|  \leq  i Ci , which implies that fpI (u) = \| s(u)  -  p\|  = 0.
6.3. Sum of squares optimization. More generally, we can consider the problem of finding a feasible point in the intersection of the cone \Sigma [x]2d with any affine
subspace. This allows us to solve sum of squares optimization problems involving
univariate polynomials. Let \scrB  : \BbbR [x]2d \rightarrow  \BbbR m be a linear map. Given b \in  \BbbR m ,we want to find p \in  \Sigma [x]2d so that \scrB (p) = b. This is equivalent to minimizing thequadratic-penalized problem
(6.2)

2

f\scrB  (u) = \| \scrB (\sigma (u))  -  b\|  .

Corollary 6.3. Suppose there exists p \in  \Sigma [x]2d such that \scrB (p) = b. Then\nabla f\scrB  (u) = 0 and \nabla 2 f\scrB  (u) \succeq  0 implies that f\scrB  (u) = 0.
Proof. The gradient and Hessian of the objective (6.2) can be written as1\nabla f\scrB  (u)(v) = \langle \scrB  (\scrA u (v)), \scrB (\sigma (u)  -  p)\rangle  ,4

1 2
2\nabla  f\scrB  (u)(v, v) = \langle \scrB  (\sigma (v)), \scrB (\sigma (u)  -  p)\rangle  + 2 \| \scrB (\scrA u (v))\|  .
4Thus by the linearity of \scrB  we can use the same construction as in the certificate (5.3)
to show that f\scrB  (u) = 0.
7. Implementation and experiments. In this section we describe an efficient
implementation of finding a sum of squares decomposition of trigonometric polynomials. A trigonometric polynomial of degree-d is defined by 2d + 1 coefficients andhas the formp(t) = a0 +

d
\sum 

(ak cos(kt) + a - k sin(kt)).

k=1

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2058

BENO\^IT LEGAT, CHENYANG YUAN, AND PABLO PARRILO

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

22x
By the substitution cos(t) = 1 - x
1+x2 and sin(t) = 1+x2 , p(x) becomes a rational function
with the denominator a power of 1 + x2 and the numerator a degree-2d polynomial inx. Thus certifying the nonnegativity of the numerator is equivalent to certifying thenonnegativity of p(t). By this correspondence the result of Theorem 1.1 also applies
to trigonometric polynomials.
the proof of Theorem 1.1 does not depend on the norm used for fp (u) =\bigm\|  Since\sum  2 \bigm\| 2\bigm\|  , we can choose one most suitable for the gradient computation. For\bigm\| p  - i ui
the rest of this section we assume that d is even for simplicity of notation; a similar
decomposition exists for odd d by choosing ``half-angles"" (see [30] for more details).
We then choose the inner product defined by evaluation at 2d + 1 points on the circle,
2d+1\langle p, q\rangle  =\sum 1p(xk )q(xk ),2d + 1k=1

xk =2k\pi .
2d + 1Since a trigonometric polynomial of degree-d is uniquely defined by evaluation on
2
2d + 1 unique points, \| p(x)\|  = 0 if and only if p is identically zero.
Let U \in  \BbbR (d+1)\times r be a matrix with column Ui representing the coefficients ofui (x), and B \in  \BbbR (d+1)\times (2d+1) be the evaluation map on 2d + 1 points with columns\bigl[ Bk = 1cos(xk ) \cdot  \cdot  \cdot  cos( d2 xk )\bigr] \top sin(xk ) \cdot  \cdot  \cdot  sin( d2 xk ) ,so that Bk\top  Ui = ui (xk ). Let p\= be the vector of coefficients of p(x), so that Bk\top  p\= = p(xk ).
Then we can write
2d+1\Bigr) 2\sum  \Bigl( \bigm\| \bigm\| 1\bigm\| U \top  Bk \bigm\| 2  -  p(xk ) ,2d + 1
k=1\Bigl( \bigm\| \Bigr) \bigm\| 2
4\nabla fp (U ) =U \top  B Diag \bigm\| U \top  Bk \bigm\|   -  p(xk ) B \top  ,
2d + 1\Bigr) 
\Bigl( \bigm\| \bigm\| \bigm\| 2\bigm\| 2
where Diag \bigm\| U \top  Bk \bigm\|   -  p(xk ) is a diagonal matrix with \bigm\| U \top  Bk \bigm\|   -  p(xk ) as thefp (U ) =kth diagonal entry. Since matrix-vector multiplication by B is equivalent to a discrete
Fourier transform, \nabla fp (U ) can be computed in O(rd log d) time using the FFT. Theorem 1.1 shows that spurious local minima do not exist when r \geq  2, so we can pickr to be a constant and obtain a near-linear iteration complexity. This is in contrast
to other SDP-based algorithms and custom interior point methods for solving thisproblem, which run into computational difficulties even when 2d = 10,000.
We implemented our algorithm for finding the sum of squares decomposition of
trigonometric polynomials in Julia,9 using the FFTW.jl [19] package for FFTs tocompute \nabla fp (U ) and the NLopt.jl [25] package to minimize fp (U ) using a first-orderalgorithm (L-BFGS). We performed the timing experiments on Intel Xeon Platinum
8260 processors, allocating at least r + 1 cores to each run, using polynomials ofdegree-2d ranging from 2,000 to 1,000,000. The test polynomials are generated withcoefficients drawn from a standard normal distribution, with a constant coefficient
added so that they all have a small positive minimum value. U is initialized with asmall random value; its magnitude depends on the size of the problem. The algorithm
is terminated when the relative error for each entry of U is on the order of 10 - 7 .
Although r = 2 is sufficient, the results in Table 1(b) shows that r = 4 minimizes
the total computational cost, as measured by the total number of FFT calls (by far
9 The code and data required to reproduce the results in this section can be found in [28].

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

LOW-RANK UNIVARIATE SUM OF SQUARES

2059

Fig. 2. Value of fp (u) against iterations of L-BFGS for computing the sum of squares decomposition of 20 random nonnegative trigonometric polynomials (2d = 100, 000), showing a linear
convergence rate.

the most expensive operation) needed for convergence. In addition, since the matrixvector products can be easily parallelized across multiple threads, increasing r does
not incur a significant per-iteration cost if sufficient threads are used. Thus we choose
r = 4 for our large-scale experiments in Table 1a. Figure 2 plots the convergence rateof 20 instances, and we can see that they achieve a linear convergence rate. This is
in contrast to grid-based methods [41, 17] which scale sublinearly in accuracy.
8. Conclusion. When does it make sense to solve nonconvex formulations ofconvex problems? In this paper we addressed this question for sum of squares decomposition and optimization of univariate polynomials, showing that solving thenonconvex formulation can provide a large computational speedup while still maintaining provable guarantees on the convergence to the global optima. Key to ourapproach is retaining polynomial structure in the nonconvex formulation. This enables us to use algebraic methods to construct a certificate showing that all SOCPs
are global minima.
Our approach for finding sum of squares decompositions generalizes to multivariate polynomials, although we do not have guarantees for the rank needed to exclude
spurious second-order critical points. On the other hand, results for low-rank matrix
factorization tell us that this rank is equal to the Pythagoras number for quadratic
forms. Thus we conjecture that a version of Theorem 1.1 is true for ternary quartics
and matrix polynomials, cases where nonnegativity is equivalent to the existence of asum of squares decomposition. Some similarities between our conditions and a new
characterization of theses cases in terms of varieties of minimal degree [6] also suggestthat Theorem 1.1 could be generalized to these cases. In particular, the case where
the syzygy module only contains the Koszul syzygies [16, p. 581] could generalize thecoprime case studied in subsection 4.1.
Another direction for future work is to apply our methods to other structured
semidefinite programs or polynomial-valued objectives such as symmetric tensor decomposition.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

2060

BENO\^IT LEGAT, CHENYANG YUAN, AND PABLO PARRILO

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

Acknowledgment. We thank the two anonymous referees for their valuable
feedback and comments.
REFERENCES[1] A. S. Bandeira, N. Boumal, and V. Voroninski, On the low-rank approach for semidefinite
programs arising in synchronization and community detection, in Proceedings of the 29th
Conference on Learning Theory, Proc. Mach. Learn. Res. 49, 2016, pp. 361--382.
[2] A. Barvinok, A remark on the rank of positive semidefinite matrices subject toaffine constraints, Discrete Comput. Geom., 25 (2001), pp. 23--31, https://doi.org/
10.1007/s004540010074.
[3] S. Bhojanapalli, N. Boumal, P. Jain, and P. Netrapalli, Smoothed analysis for low-ranksolutions to semidefinite programs in quadratic penalty form, in Proceedings of the 31st
Conference On Learning Theory, Proc. Mach. Learn. Res. 75, S. Bubeck, V. Perchet, andP. Rigollet, eds., 2018, pp. 3243--3270.
[4] S. Bhojanapalli, B. Neyshabur, and N. Srebro, Global optimality of local search for low
rank matrix recovery, in Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS'16, 2016, pp. 3880--3888.
[5] G. Blekherman, P. A. Parrilo, and R. R. Thomas, eds., Semidefinite Optimization andConvex Algebraic Geometry, MOS-SIAM Ser. Optim. 13, SIAM, Philadelphia, 2013.
[6] G. Blekherman, D. Plaumann, R. Sinn, and C. Vinzant, Low-rank sum-of-squares representations on varieties of minimal degree, Int. Math. Res. Not. IMRN, 2019, pp. 33--54.
[7] N. Boumal, V. Voroninski, and A. Bandeira, The non-convex Burer-Monteiro approach works on smooth semidefinite programs, in Proceedings of Advances in
Neural Information Processing Systems, D. Lee, M. Sugiyama, U. Luxburg, I.
Guyon, and R. Garnett, eds., 2016; also available online from https://proceedings.
neurips.cc/paper/2016/file/3de2334a314a7a72721f1f74a6cb4cee-Paper.pdf.
[8] N. Boumal, V. Voroninski, and A. S. Bandeira, Deterministic guarantees for BurerMonteiro factorizations of smooth semidefinite programs, Comm. Pure Appl. Math., 73(2020), pp. 581--608.
[9] S. Burer and R. D. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95 (2003), pp. 329--357,
https://doi.org/10.1007/s10107-002-0352-8.
[10] S. Burer and R. D. Monteiro, Local minima and convergence in low-rank semidefinite programming, Math. Program., 103 (2005), pp. 427--444, https://doi.org/10.1007/s10107-0040564-1.
[11] Y. Chi, Y. M. Lu, and Y. Chen, Nonconvex optimization meets low-rank matrix factorization: An Overview , IEEE Trans. Signal Process., 67 (2019), pp. 5239--5269,
https://doi.org/10.1109/TSP.2019.2937282.
[12] M.-D. Choi, T. Y. Lam, and B. Reznick, Sums of squares of real polynomials, in K-Theory
and Algebraic Geometry: Connections with Quadratic Forms and Division Algebras, Part
2, Proc. Sympos. Pure Math. 58, American Mathematical Society, Providence, RI, 1995,
pp. 103--126, https://doi.org/10.1090/pspum/058.2/1327293.
[13] D. Cifuentes, On the Burer-Monteiro method for general semidefinite programs, Optim. Lett.,
15 (2021), pp. 2299--2309.
[14] D. Cifuentes and A. Moitra, Polynomial Time Guarantees for the Burer-Monteiro Method,
https://arxiv.org/abs/1912.01745, 2019.
[15] D. Cifuentes and P. A. Parrilo, Sampling algebraic varieties for sum of squares programs,
SIAM J. Optim., 27 (2017), pp. 2381--2404, https://doi.org/10.1137/15M1052548.
[16] D. A. Cox, J. Little, and D. O'Shea, Ideals, Varieties, and Algorithms, Springer, New York,
2015.
[17] B. Dumitrescu, Positive Trigonometric Polynomials and Signal Processing Applications, Signals Commun. Technol. 103, Springer, New York, 2007.
[18] D. Dummit and R. Foote, Abstract Algebra, Wiley, New York, 2003.
[19] M. Frigo and S. G. Johnson, The design and implementation of FFTW3, Proc. IEEE, 93(2005), pp. 216--231.
[20] R. Ge, F. Huang, C. Jin, and Y. Yuan, Escaping from saddle points---Online stochastic
gradient for tensor decomposition, in Proceedings of the Conference on Learning Theory,
2015, pp. 797--842.
[21] R. Ge, C. Jin, and Y. Zheng, No spurious local minima in nonconvex low rank problems: A
unified geometric analysis, in Proceedings of the 34th International Conference on Machine
Learning, J. Mach. Learn. Res. 70, 2017, pp. 1233--1242.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Downloaded 08/19/23 to 73.47.183.48 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

LOW-RANK UNIVARIATE SUM OF SQUARES

2061[22] R. Ge, J. D. Lee, and T. Ma, Matrix completion has no spurious local minimum, in Proceedings of the 30th International Conference on Neural Information Processing Systems,
NIPS'16, 2016, pp. 2981--2989.
[23] R. W. Hamming, Numerical Methods for Scientists and Engineers, McGraw-Hill, New York,1973.
[24] C. Jin, R. Ge, P. Netrapalli, S. M. Kakade, and M. I. Jordan, How to escape saddle
points efficiently, in Proceedings of the International Conference on Machine Learning,
Proc. Mach. Learn. Res. 70, 2017, pp. 1724--1732.
[25] S. G. Johnson, The NLopt Nonlinear-Optimization Package, 2014.
[26] L. Kapelevich, C. Coey, and J. P. Vielma, Sum of squares generalizations for conic sets,
Math. Program., 199 (2023), pp. 1417--1429, https://doi.org/10.1007/s10107-022-01831-6.
[27] M. Laurent, Sums of squares, moment matrices and optimization over polynomials, in Emerging Applications of Algebraic Geometry, Springer, New York, 2009, pp. 157--270.
[28] B. Legat, C. Yuan, and P. A. Parrilo, Low-rank univariate sum of squares has no spurious
local minima, 2023, https://doi.org/10.24433/CO.7364738.v1.
[29] Q. Li, Z. Zhu, and G. Tang, The non-convex geometry of low-rank matrix optimization, Inf.
Inference, 8 (2019), pp. 51--96.
[30] J. Lofberg and P. Parrilo, From coefficients to samples: A new approach to SOS optimization, in Proceedings of the 43rd IEEE Conference on Decision and Control (CDC), IEEE,
2004, pp. 3154--3159, https://doi.org/10.1109/CDC.2004.1428957.
[31] D. Papp, Univariate polynomial optimization with sum-of-squares interpolants, in Modelingand Optimization: Theory and Applications, Springer, New York, 2017, pp. 143--162.
[32] P. A. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods inRobustness and Optimization, Ph.D. thesis, California Institute of Technology, 2000.
[33] P. A. Parrilo, Polynomial games and sum of squares optimization, in Proceedings of the 45th
IEEE Conference on Decision and Control, IEEE, 2006, pp. 2855--2860.
[34] G. Pataki, On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues, Math. Oper. Res., 23 (1998), pp. 257--511 https://doi.
org/10.1287/moor.23.2.339.
[35] T. Roh and L. Vandenberghe, Discrete transforms, semidefinite programming, and sumof-squares representations of nonnegative polynomials, SIAM J. Optim., 16 (2006), pp.
939--964.
[36] C. Scheiderer, Extreme points of Gram spectrahedra of binary forms, Discrete Comput.
Geom., 67 (2022), pp. 1174--1190.
\"[37] K. Schmudgen,
The K-moment problem for compact semi-algebraic sets, Math. Ann., 289(1991), pp. 203--206.
[38] B. Sturmfels, Solving Systems of Polynomial Equations, CBMS Reg. Conf. Ser. Math. 97,
American Mathematical Society, Providence, RI, 2002.
[39] J. Sun, Q. Qu, and J. Wright, A geometric analysis of phase retrieval, Found. Comput.
Math., 18 (2018), pp. 1131--1198.
[40] I. Waldspurger and A. Waters, Rank optimality for the Burer-Monteiro factorization, SIAM
J. Optim., 30 (2020), pp. 2577--2602.
[41] S.-P. Wu, S. Boyd, and L. Vandenberghe, FIR filter design via spectral factorizationand convex optimization, in Applied and Computational Control, Signals, and Circuits,
Springer, New York, 1999, pp. 215--245.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.