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\'ez 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.
翻译:在离散时间信号处理过程中,验证三角数多元数字的假设性是设计问题的第一要务。从Riesz-Fej\'ez光谱因子化理论中可以清楚地知道,单位圆上的任何三角数单异多元数字正数都可以分解成具有复杂系数的Hermitian正方形。在这里,我们侧重于使用高斯的整数系数(即真实和想象的缩略系数)的多数值案例。我们设计、分析和比较了理论上和实际上的三种混合数字-顺数算法,从理论上和实际上计算了Hermitian 方形的加权数,在单位圆上计算出任何三角数单异数多元数字正数的加权数,加上高斯系数。第一个和第二个算法所依赖的数值步骤分别是复杂的根隔离和半确定性程序。由于补偿技术,赫米特所选择的直径直径方平方平方平方平方平方平方正值的精确和精确比数计算法,也是基于复杂半确定性精度的半确定性方位数公式的第三算法,我们所估计的精确度的精确度的精确度和精确度计算。