论文标题
计算有限的Abelian组的稀疏傅立叶总和在准线性时间
Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
论文作者
论文摘要
在有限的阿贝尔群体上验证功能的非负性问题是一个长期的挑战性问题。有限群体的代表理论的基本理论表明，有限的Abelian组$ G $的功能$ f $可以写成$ f（x）= \ sum_ {χ{χ{χ{χ{χ $ g $的双组由$ g $的所有字符和$ \ wideHat {f}（χ）$组成，是$ f $ in $χ\ in \ wideHat {g} $的傅立叶系数。在本文中，我们表明，通过执行快速（逆）傅立叶变换，我们能够在有限的Abelian Group $ G $上计算出稀疏的傅立叶正方形（FSO）证书（fsos）证书，具有复杂性\如果$ \ operatateRorname {operatateRorname {o} \ weft（| g | \ log（| g |）+\ log（k _ {\ min}）\ protatorName {sdp}（2k _ {\ min}）\ right）$，\ fi，\ fi是quasi-linear，按$ g $ and polynomial的顺序为fsos sparsity \ $ k _ min} $ g $ g $ and polynomial。此外，对于有限的Abelian Group $ g $和set $ s \ subset \ wideHat {g} $的非Negatvie函数$ f $，我们给出了常数$ m $的下限，以便$ f+m $承认支持在} $ s $上支持的FSO。我们通过数值实验在各种Abelian订单组上进行了最高$ 10^7 $的数值实验来证明所提出的算法的效率。作为应用程序，我们还解决了一些组合优化问题和赫尔米尔人正方形（SOHS）问题的总和，如果在$ \ mathbb {t}^n $ \ fi上，稀疏FSOS。
The problem of verifying the nonnegativity of a function on a finite abelian group is a long-standing challenging problem. The basic theory of representation theory of finite groups indicates that a function $f$ on a finite abelian group $G$ can be written as a linear combination of characters of irreducible representations of $G$ by $ f(x)=\sum_{χ\in \widehat{G}} \widehat{f} (χ)χ(x)$, where $\widehat{G}$ is the dual group of $G$ consisting of all characters of $G$ and $ \widehat{f} (χ)$ is the Fourier coefficient of $f$ at $χ\in \widehat{G}$. In this paper, we show that by performing the fast (inverse) Fourier transform, we are able to compute a sparse Fourier sum of squares (FSOS) certificate of $f$ on a finite abelian group $G$ with complexity \if $\operatorname{O}\left(|G| \log(|G|)+\log(k_{\min})\operatorname{SDP}(2k_{\min})\right)$,\fi that is quasi-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 finite abelian group $G$ and a set $S \subset \widehat{G}$, we give a lower bound of the constant $M$ such that $f+M$ admits an FSOS supported on} $S$. We demonstrate the efficiency of the proposed algorithm by numerical experiments on various abelian groups of orders up to $10^7$. As applications, we also solve some combinatorial optimization problems and the sum of Hermitian squares (SOHS) problem \if on $\mathbb{T}^n$\fi by sparse FSOS.
