Low-complexity RLS algorithms using dichotomous coordinate descent iterations

Article English OPEN
Zakharov, Yuriy V. ; White, George P. ; Liu, Jie (2008)
  • Subject: 1711 | 2208
    arxiv: Computer Science::Sound

In this paper, we derive low-complexity recursive least squares (RLS) adaptive filtering algorithms. We express the RLS problem in terms of auxiliary normal equations with respect to increments of the filter weights and apply this approach to the exponentially weighted and sliding window cases to derive new RLS techniques. For solving the auxiliary equations, line search methods are used. We first consider conjugate gradient iterations with a complexity of O(N-2) operations per sample; N being the number of the filter weights. To reduce the complexity and make the algorithms more suitable for finite precision implementation, we propose a new dichotomous coordinate descent (DCD) algorithm and apply it to the auxiliary equations. This results in a transversal RLS adaptive filter with complexity as low as 3N multiplications per sample, which is only slightly higher than the complexity of the least mean squares (LMS) algorithm (2N multiplications). Simulations are used to compare the performance of the proposed algorithms against the classical RLS and known advanced adaptive algorithms. Fixed-point FPGA implementation of the proposed DCD-based RLS algorithm is also discussed and results of such implementation are presented.
  • References (30)
    30 references, page 1 of 3

    [1] S. Haykin, Adaptive Filtering, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 1991.

    [2] A. H. Sayed, Fundamentals of Adaptive Filtering. Hoboken, NJ: Wiley, 2003.

    [3] I. D. Skidmore and I. K. Proudler, “The KaGE RLS algorithm,” IEEE Trans. Signal Process., vol. 51, no. 12, pp. 3094-3104, Dec. 2003.

    [4] J. H. Husoy, “Adaptive filters viewed as iterative linear equation solvers,” in Lecture Notes in Computer Science: Numerical Analysis and Its Applications. Berlin, Germany: Springer-Verlag, 2005, vol. 3401/2005, pp. 320-327.

    [5] G. K. Boray and M. D. Srinath, “Conjugate gradient techniques for adaptive filtering,” IEEE Trans. Circuits Syst. I: Fundam. Theory Appl., vol. 39, no. 1, pp. 1-10, 1992.

    [6] T. Bose and M. Q. Chen, “Conjugate gradient method in adaptive bilinear filtering,” IEEE Trans. Signal Process., vol. 43, no. 6, pp. 1503-1508, 1995.

    [7] P. S. Chang and A. N. Willson, Jr., “Analysis of conjugate gradient algorithms for adaptive filtering,” IEEE Trans. Signal Process., vol. 48, no. 2, pp. 409-418, Feb. 2000.

    [8] O. Diene and A. Bhaya, “Adaptive filtering algorithms designed using control Liapunov functions,” IEEE Signal Process. Lett., vol. 13, no. 4, pp. 224-227, 2006.

    [9] T. Bose and G. F. Xu, “The Euclidean direction search algorithm in adaptive filtering,” IEICE Trans. Fundam., vol. E85-A, no. 3, pp. 532-539, Mar. 2002.

    [10] G. F. Xu and T. Bose, “Analysis of the Euclidean direction set adaptive algorithm,” in Proc. ICASSP'98, Seattle, WA, May 12-15, 1998, vol. 3, pp. 1689-1692.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    White Rose Research Online - IRUS-UK 0 129
Share - Bookmark