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:
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.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.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
csos3to 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:
csos1is the clear winner for speed. For a degree-250 polynomial,csos1finished in 120 seconds, whilecsos2took about 3 hours andcsos3took nearly 7 hours. - Bit Complexity: The authors established rigorous bounds.
csos1has 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