Exact SOHS Decompositions of Trigonometric Univariate Polynomials with Gaussian Coefficients

Victor Magron, Mohab Safey El Din, Markus Schweighofer, Trung Hieu Vu

This paper, presented at ISSAC '22, tackles a fundamental problem in digital signal processing: how to prove that a trigonometric polynomial is always non-negative. While numerical solvers can give us an "almost certain" answer, this research provides three new algorithms to compute exact mathematical proofs (decompositions) that these polynomials are positive, even when dealing with complex "Gaussian" coefficients.

TL;DR

The authors present three hybrid numeric-symbolic algorithms to compute exact Sum of Hermitian Squares (SOHS) decompositions for trigonometric polynomials with Gaussian integer coefficients. These algorithms bridge the gap between fast but imprecise numerical solvers and the need for rigorous, exact certification in applications like digital filter design.

What Problem Does This Paper Address?

In discrete-time signal processing, we often work with trigonometric polynomials—mathematical functions used to describe filters and signals. A critical requirement for many design problems (like ensuring a filter doesn't amplify noise) is certifying that a polynomial remains non-negative or positive over the entire unit circle.

The classic Riesz-Fejér theorem tells us that any such non-negative polynomial can be written as a "Hermitian square" (a complex version of a squared number). However, finding this decomposition is usually done with numerical tools like Semidefinite Programming (SDP). These tools provide approximate floating-point answers that might be "close enough" for a simulation but aren't mathematically exact. For high-stakes engineering or formal verification, we need an exact decomposition using rational numbers.

The challenge is that moving from an approximate numerical result to an exact symbolic one is computationally expensive and mathematically non-trivial, especially when the polynomial's coefficients are Gaussian integers (complex numbers $a + bi$ where $a$ and $b$ are integers).

Methods

The authors propose a "hybrid" approach: use fast numerical methods to get a "good guess," then use symbolic techniques to "clean up" the result into an exact proof. They introduce three algorithms:

  1. csos1 (Root Isolation): This algorithm finds the complex roots of a slightly perturbed version of the input polynomial. By isolating these roots with high precision, it constructs an approximate decomposition and then calculates a "remainder" to compensate for the difference, resulting in an exact SOHS.
  2. csos2 (SDP + Compensation): Similar to the first, but it uses complex Semidefinite Programming to find an approximate "Gram matrix" (a matrix representation of the squares). It then uses a compensation technique to handle the numerical errors.
  3. csos3 (Rounding and Projection): This is an adaptation of an algorithm by Peyrl and Parrilo. It takes the numerical output of an SDP solver, rounds the values to rational numbers, and then "projects" them back into the space of valid solutions to ensure all mathematical constraints are satisfied exactly.

Datasets

The researchers evaluated their algorithms using two main approaches:

  • Random Benchmarks: They generated families of trigonometric polynomials with Gaussian integer coefficients of varying degrees (from $d=50$ to $d=250$) to test scaling and speed.
  • Filter Design Case Study: They applied csos3 to a real-world engineering problem: designing a linear-phase Finite Impulse Response (FIR) filter with certified stopband energy bounds.

Key Insights and Ideas

  • The Power of Perturbation: A core "aha" moment is that you shouldn't try to decompose the original polynomial $f$ directly. Instead, you decompose $f - \epsilon$ (where $\epsilon$ is a tiny positive value). This "gap" provides the mathematical room needed to absorb the numerical errors generated during the computation.
  • Complexity Trade-offs: The authors prove that all three algorithms have "polynomial bit complexity." This means the time they take to run grows predictably as the degree or the size of the coefficients increases.
  • Root Isolation vs. SDP: Theoretically and practically, the root-isolation method (csos1) is significantly faster for simple positivity checks. However, SDP-based methods (csos2/3) are more versatile because they can handle additional engineering constraints (like those found in filter design) that root isolation cannot.

Key Results

  • Performance: csos1 is the clear winner for speed. For a degree-250 polynomial, csos1 finished in 120 seconds, while csos2 took about 3 hours and csos3 took nearly 7 hours.
  • Bit Complexity: The authors established rigorous bounds. csos1 has a complexity of $\tilde{O}(d^6(d+\tau))$, while the SDP-based methods are $\tilde{O}(d^{13}(d+\tau)^2)$.
  • Certified Engineering: They successfully designed a certified FIR filter, providing an exact lower bound on stopband energy ($4.461503 \times 10^{-5}$) in just 0.74 seconds.

Limitations and Future Work

  • Strict Positivity: The current algorithms require the polynomial to be strictly positive on the unit circle. If the polynomial has roots exactly on the circle (i.e., it touches zero), the "perturbation" method fails. Handling these "boundary" cases is a target for future research.
  • The Multivariate Leap: These results are for univariate polynomials (one variable). Extending exact SOHS decompositions to multivariate trigonometric polynomials is significantly more complex and remains an open challenge for the field.

Summary updated

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 non-negative 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.
BibTeX
@inproceedings{magron2022exact,
  author = {Victor Magron and Mohab Safey El Din and Markus Schweighofer and Trung Hieu Vu},
  title = {{Exact SOHS Decompositions of Trigonometric Univariate Polynomials with Gaussian Coefficients}},
  booktitle = {ISSAC},
  year = {2022},
  url = {https://openreview.net/forum?id=tBnK9StvmN},
}

Loading related content...

Figure