Recursive Total Least-Squares Algorithm Based on Inverse Power Method and Dichotomous Coordinate-Descent Iterations

Reza Arablouei, Kutluyil Dogançay, Stefan WernerIEEE TSP 2014 · DOI · OpenReview

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:

  1. Inverse Power Method: This method is used to estimate the minor eigenvector of the data covariance matrix, which corresponds to the optimal TLS solution.
  2. 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.

Table comparing the computational complexity of DCD-RTLS against AIP, xRTLS, and kRTLS for shift-structured and non-shift-structured inputs.

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.

Comparison of hardware gate counts for various RTLS algorithms as a function of system order.

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

Abstract

We develop a recursive total least-squares (RTLS) algorithm for errors-in-variables system identification utilizing the inverse power method and the dichotomous coordinate-descent (DCD) iterations. The proposed algorithm, called DCD-RTLS, outperforms the previously-proposed RTLS algorithms, which are based on the line-search method, with reduced computational complexity. We perform a comprehensive analysis of the DCD-RTLS algorithm and show that it is asymptotically unbiased as well as being stable in the mean. We also find a lower bound for the forgetting factor that ensures mean-square stability of the algorithm and calculate the theoretical steady-state mean-square deviation (MSD). We verify the effectiveness of the proposed algorithm and the accuracy of the predicted steady-state MSD via simulations.
BibTeX
@article{arablouei2014recursive,
  author = {Reza Arablouei and Kutluyil Dogançay and Stefan Werner},
  title = {{Recursive Total Least-Squares Algorithm Based on Inverse Power Method and Dichotomous Coordinate-Descent Iterations}},
  journal = {IEEE Trans. Signal Process.},
  year = {2014},
  doi = {10.1109/tsp.2015.2405492},
}
Figure