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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of maximizing the geometric mean of $d$ low-degreenon-negative forms on the real or complex sphere in $n$ variables. We show thatthis highly non-convex problem is NP-hard even when the forms are quadratic andis equivalent to optimizing a homogeneous polynomial of degree $O(d)$ on thesphere. The standard Sum-of-Squares based convex relaxation for this polynomialoptimization problem requires solving a semidefinite program (SDP) of size$n^{O(d)}$, with multiplicative approximation guarantees of$\Omega(\frac{1}{n})$. We exploit the compact representation of this polynomialto introduce a SDP relaxation of size polynomial in $n$ and $d$, and prove thatit achieves a constant factor multiplicative approximation when maximizing thegeometric mean of non-negative quadratic forms. We also show that this analysisis asymptotically tight, with a sequence of instances where the gap between therelaxation and true optimum approaches this constant factor as $d \rightarrow\infty$. Next we propose a series of intermediate relaxations of increasingcomplexity that interpolate to the full Sum-of-Squares relaxation, as well as arounding algorithm that finds an approximate solution from the solution of anyintermediate relaxation. Finally we show that this approach can be generalizedfor relaxations of products of non-negative forms of any degree.

Semidefinite Relaxations of Products of Nonnegative Forms on the Sphere