English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the problem of decomposing a polynomial $p$ into a sum of $r$squares by minimizing a quadratically penalized objective $f_p(\mathbf{u}) =\left\lVert \sum_{i=1}^r u_i^2 - p\right\lVert^2$. This objective is nonconvexand is equivalent to the rank-$r$ Burer-Monteiro factorization of asemidefinite program (SDP) encoding the sum of squares decomposition. We showthat for all univariate polynomials $p$, if $r \ge 2$ then $f_p(\mathbf{u})$has no spurious second-order critical points, showing that all local optima arealso global optima. This is in contrast to previous work showing that forgeneral SDPs, in addition to genericity conditions, $r$ has to be roughly thesquare root of the number of constraints (the degree of $p$) for there to be nospurious second-order critical points. Our proof uses tools from computationalalgebraic geometry and can be interpreted as constructing a certificate usingthe first- and second-order necessary conditions. We also show that by choosinga norm based on sampling equally-spaced points on the circle, the gradient$\nabla f_p$ can be computed in nearly linear time using fast Fouriertransforms. Experimentally we demonstrate that this method has very fastconvergence using first-order optimization algorithms such as L-BFGS, withnear-linear scaling to million-degree polynomials.

Low-Rank Univariate Sum of Squares Has No Spurious Local Minima