Abstract: Certifying the positivity of trigonometric polynomials is of first importance for design problems in discrete-time signal processing. It is well known from the Riesz-Fejér spectral factorization theorem that any trigonometric univariate polynomial positive on the unit circle can be decomposed as a Hermitian square with complex coefficients. Here we focus on the case of polynomials with Gaussian integer coefficients, i.e., with real and imaginary parts being integers. We design, analyze and compare, theoretically and practically, three hybrid numeric-symbolic algorithms computing weighted sums of Hermitian squares decompositions for trigonometric univariate polynomials positive on the unit circle with Gaussian coefficients. The numerical steps the first and second algorithm rely on are complex root isolation and semidefinite programming, respectively. An exact sum of Hermitian squares decomposition is obtained thanks to compensation techniques. The third algorithm, also based on complex semidefinite programming, is an adaptation of the rounding and projection algorithm by Peyrl and Parrilo. For all three algorithms, we prove bit complexity and output size estimates that are polynomial in the degree of the input and linear in the maximum bitsize of its coefficients. We compare their performance on randomly chosen benchmarks, and further design a certified finite impulse filter.
Introduction
In discrete-time signal processing, trigonometric polynomials are essential for describing filters and signals. A critical requirement for many design problems, such as ensuring a filter does not amplify noise, is certifying that a polynomial remains non-negative or positive over the entire unit circle. While the classic Riesz-Fejér theorem guarantees that such polynomials can be written as a "Hermitian square," finding this decomposition exactly is computationally difficult.
Numerical tools like Semidefinite Programming (SDP) provide approximate floating-point answers that are often insufficient for high-stakes engineering or formal verification. This research bridges the gap by providing three hybrid numeric-symbolic algorithms to compute exact Sum of Hermitian Squares (SOHS) decompositions for polynomials with Gaussian integer coefficients (complex numbers $a + bi$ where $a, b \in \mathbb{Z}$).
Hybrid Numeric-Symbolic Methodology
The proposed approach uses fast numerical methods to generate a high-precision approximation, which is then refined into an exact symbolic proof using compensation techniques. The three algorithms are:
csos1(Root Isolation): This algorithm isolates the complex roots of a slightly perturbed version of the input polynomial. By using high-precision root isolation, it constructs an approximate decomposition and calculates a "remainder" to compensate for numerical differences, resulting in an exact SOHS.csos2(SDP + Compensation): This method uses complex SDP to find an approximate Gram matrix (a matrix representation of the squares) and applies compensation to handle numerical errors.csos3(Rounding and Projection): Adapted from Peyrl and Parrilo, this algorithm rounds numerical SDP output to rational numbers and projects them back into the space of valid solutions to satisfy mathematical constraints exactly.
A core insight of these methods is the use of perturbation. Rather than decomposing the original polynomial $f$ directly, the algorithms decompose $f - \epsilon$. This small positive gap $\epsilon$ provides the mathematical "room" necessary to absorb numerical errors during the symbolic cleanup phase.
Performance and Complexity
The researchers evaluated these algorithms using random benchmarks of varying degrees (from $d=50$ to $d=250$) and a real-world filter design case study.
As shown in Table 1, csos1 is significantly faster than the SDP-based methods. For a degree-250 polynomial, csos1 finished in 120 seconds, whereas csos2 and csos3 took approximately 3 and 7 hours, respectively. Theoretically, the authors established that csos1 has a bit complexity of $\tilde{O}(d^6(d+\tau))$, while the SDP-based methods are $\tilde{O}(d^{13}(d+\tau)^2)$. Despite the speed of csos1, SDP-based methods remain valuable for their versatility in handling additional engineering constraints.
Conclusion
This work provides a robust framework for certifying the positivity of trigonometric polynomials with exactness. While the current algorithms require strict positivity on the unit circle, they represent a significant step forward for formal verification in signal processing. Future research aims to address polynomials with roots on the unit circle and extend these techniques to the multivariate case.
Summary updated