2022/01/11 by Jianting Yang, Ke Ye, Yang, Jianting +3
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #FOS: Mathematics #Finite Group Theory Research #Optimization and Control (math.OC) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2201.03912
openalex publication_date 2022/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)=∑_χ∈ \widehatG \widehatf (χ)χ(x), where \widehatG is the dual group of G consisting of all characters of G and \widehatf (χ) is the Fourier coefficient of f at χ∈ \widehatG. 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 O(|G| log(|G|)+log(kmin)SDP(2kmin)),\fi that is quasi-linear in the order of G and polynomial in the FSOS sparsity \if kmin\fi of f. Moreover, for a nonnegatvie function f on a finite abelian group G and a set S ⊂ \widehatG, 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 107. As applications, we also solve some combinatorial optimization problems and the sum of Hermitian squares (SOHS) problem \if on \mathbbTn\fi by sparse FSOS.