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

The problem of verifying the nonnegativity of a function on a finite abeliangroup is a long-standing challenging problem. The basic theory ofrepresentation theory of finite groups indicates that a function $f$ on afinite abelian group $G$ can be written as a linear combination of charactersof irreducible representations of $G$ by $ f(x)=\sum_{\chi \in \widehat{G}}\widehat{f} (\chi)\chi(x)$, where $\widehat{G}$ is the dual group of $G$consisting of all characters of $G$ and $ \widehat{f} (\chi)$ is the Fouriercoefficient of $f$ at $\chi \in \widehat{G}$. In this paper, we show that byperforming the fast (inverse) Fourier transform, we are able to compute asparse Fourier sum of squares (FSOS) certificate of $f$ on a finite abeliangroup $G$ with complexity \if $\operatorname{O}\left(|G|\log(|G|)+\log(k_{\min})\operatorname{SDP}(2k_{\min})\right)$,\fi that isquasi-linear in the order of $G$ and polynomial in the FSOS sparsity \if$k_{\min}$\fi of $f$. Moreover, for a nonnegatvie function $f$ on a finiteabelian group $G$ and a set $S \subset \widehat{G}$, we give a lower bound ofthe constant $M$ such that $f+M$ admits an FSOS supported on} $S$. Wedemonstrate the efficiency of the proposed algorithm by numerical experimentson various abelian groups of orders up to $10^7$. As applications, we alsosolve some combinatorial optimization problems and the sum of Hermitian squares(SOHS) problem \if on $\mathbb{T}^n$\fi by sparse FSOS.

Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time