Introduction
In the field of signal processing, system identification typically relies on Least Squares (LS) techniques. However, LS assumes that noise only affects the output measurements. In many real-world scenarios, such as control systems and econometrics, the input data is also corrupted by noise—a situation described by the Errors-in-Variables (EIV) model. Total Least Squares (TLS) is the standard approach for EIV models, but its recursive implementation (RTLS) is often computationally prohibitive for real-time hardware due to complex optimization requirements.
The DCD-RTLS Approach
This paper introduces DCD-RTLS, a highly efficient recursive algorithm designed for real-time hardware implementation. The algorithm combines two key techniques to minimize computational overhead:
- Inverse Power Method: This method is used to estimate the minor eigenvector of the data covariance matrix, which corresponds to the optimal TLS solution.
- Dichotomous Coordinate-Descent (DCD) Iterations: DCD is a "shift-and-add" algorithm that solves the linear equations required by the inverse power method. By replacing multiplications with bit-shifts and additions, DCD significantly reduces the computational burden.
Computational Complexity Analysis
A primary advantage of DCD-RTLS is its reduced complexity. For shift-structured data, which is common in adaptive filtering, the algorithm requires only $10L + 2$ multiplications per iteration, where $L$ is the system order. This is a substantial improvement over existing methods like kRTLS, which requires $22L + 93$ multiplications.
Hardware Implementation and Gate Count
The shift-and-add nature of the DCD solver makes it exceptionally well-suited for FPGA and ASIC implementations. By avoiding costly hardware multipliers for the linear system solving step, the physical "gate count" on the chip is minimized.
As shown in the figure above, the hardware footprint of DCD-RTLS remains significantly lower than that of AIP or kRTLS as the system order increases, making it ideal for high-order system identification in resource-constrained environments.
Stability and Performance
The authors provide a rigorous stability analysis, deriving a lower bound for the forgetting factor ($\lambda$) to ensure the algorithm remains stable under varying noise conditions. Simulations demonstrate that DCD-RTLS not only achieves lower complexity but also converges faster than line-search-based algorithms like xRTLS and kRTLS. Furthermore, the theoretical steady-state Mean-Square Deviation (MSD) aligns closely with simulation results, confirming the accuracy of the mathematical model.
Conclusion
DCD-RTLS offers a robust and efficient solution for recursive TLS system identification. By leveraging the DCD algorithm to perform linear solving via bit-shifts and additions, the method achieves $O(L)$ complexity and a minimal hardware footprint without sacrificing convergence speed or accuracy. While it requires careful tuning of DCD parameters ($N, M, H$), its benefits for real-time, low-power hardware implementation are significant.
Summary updated