TL;DR
This paper introduces a novel adaptive algorithm (ARE) for efficiently tracking the roots (zeros) of time-varying polynomials, particularly those arising from z-transforms of speech signals. By solving a set of linear equations and periodically verifying with a robust factorization method, ARE offers a computationally lighter alternative to existing methods, especially for practical signal processing scenarios.
What Problem Does This Paper Address?
Estimating the zeros of z-transforms is crucial in many signal processing applications, such as speech analysis and system identification. When dealing with time-varying signals, the z-transform polynomial also changes over time, requiring frequent re-estimation of its zeros. Traditional methods for finding polynomial roots, like eigenvalue decomposition of companion matrices or factorization algorithms (e.g., Lindsey-Fox), are computationally expensive, especially for high-degree polynomials and when applied repeatedly to track changes. These methods often re-factorize from scratch for each new set of coefficients, ignoring the fact that roots of polynomials change continuously with their coefficients. This paper addresses the need for a more efficient, adaptive approach that leverages this continuity to track root changes without the prohibitive cost of full re-factorization at every step.
Methods
The core of the proposed method, Adaptive Root Estimation (ARE), lies in solving a system of linear equations to update the root vector. Instead of re-factorizing the entire polynomial at each time step, ARE estimates the change in the root vector based on the change in the polynomial's coefficients. This is achieved by reformulating the relationship between polynomial coefficients and roots in matrix form and then approximating the update.
To prevent the adaptive estimates from drifting over time, especially when coefficient changes are larger or faster than expected, the authors propose a verification step. At regular intervals, the Aberth-Ehrlich factorization method is used to re-calculate the roots. This acts as a safeguard, bounding the accumulation of estimation errors and ensuring the overall accuracy of the tracking. The paper also establishes the relationship between z-transform coefficients and zeros, and details how the adaptive estimation and verification steps are integrated into a coherent algorithm.
Datasets
The paper describes two types of datasets used for evaluation:
- Accuracy Test Datasets: These datasets consist of time-varying polynomials with varying degrees (N=3, N=4, N=81) and coefficient perturbation lengths. The coefficients are generated to simulate slow time variations over a specific time interval.
- Run Time Test Dataset: This dataset is similar to the accuracy test dataset but uses larger polynomial degrees (N=[270; 800]) to highlight asymptotic run-time tendencies.
The datasets are designed to evaluate both the accuracy of the ARE method in tracking roots and its computational efficiency compared to existing algorithms.
Key Insights and Ideas
- Leveraging Root Continuity: The fundamental insight is that polynomial roots are continuous functions of their coefficients. This means small changes in coefficients lead to small changes in roots, a property that adaptive methods can exploit for efficiency.
- Linear System for Adaptation: The paper cleverly reformulates the problem of root tracking into solving a system of linear equations, which is generally more efficient than full polynomial factorization.
- Verification as a Safeguard: The integration of a robust factorization method (Aberth-Ehrlich) at intervals is a crucial innovation. It addresses the potential weakness of adaptive methods – drifting errors – by providing periodic recalibration, thus bounding the overall error.
- Trade-off Between Speed and Accuracy: The method is most accurate when coefficients change slowly. For faster changes, the adaptive step introduces approximations, and the verification step becomes more critical.
Key Results
- Computational Efficiency: For practically sized input sequence lengths and polynomial degrees, the proposed ARE method demonstrates a lower run time compared to the Matlab
rootsfunction and the Lindsey-Fox (LF) algorithm. While ARE has an asymptotic time complexity of O(n³), it outperformsrootsin many common scenarios. - Accuracy: The ARE method provides quite accurate estimations. However, as expected, the Root Mean Square Deviation (RMSD) between estimated and true roots increases with larger coefficient perturbation lengths, indicating a tendency to drift.
- Bounded Error: The verification step with Aberth-Ehrlich effectively bounds the estimation error accumulation, preventing unbounded drift.
Limitations and Future Work
- Slow Coefficient Change Requirement: The ARE method is most effective and accurate when the polynomial coefficients exhibit a relatively slow rate of change. Large or rapid coefficient perturbations can lead to larger root perturbations and potentially less accurate estimations between verification steps.
- Dynamic Verification Heuristic: The paper suggests that a future direction would be to develop a dynamic heuristic for deciding when to apply the Aberth-Ehrlich verification, rather than relying on fixed time intervals. This would optimize the trade-off between computational cost and accuracy, especially in scenarios with varying rates of coefficient change.
- Computer and Implementation Dependency: The authors note that run-time measurements are highly dependent on the specific computer hardware and software implementation, and thus the presented results are indicative.
Summary updated