You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
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.
[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.
[11] M. Q. Chen, “A direction set based algorithm for adaptive least squares problems in signal processing,” in Applied and Computational Control, Signals and Circuits: Recent Developments. Norwell, MA: Kluwer Academic, 2001, pp. 213-236.
[12] C. E. Davila, “Line search algorithms for adaptive filtering,” Trans. Signal Process., vol. 41, no. 7, pp. 2490-2494, Jul. 1993.
[13] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed. Baltimore, MD: The Johns Hopkins Univ. Press, 1996.
[14] M. Al-Baali, “Descent property and global convergence of the FletcherReeves method with inexact line search,” IMA J. Numer. Anal., vol. 5, pp. 121-124, 1985.
[15] Z. J. Shi and J. Shen, “Convergence of nonmonotone line search method,” J. Computat. Appl. Math. Elsevier, vol. 193, pp. 397-412, 2006.
[16] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, U.K.: Cambridge Univ. Press, 2006.
[17] D. K. Faddeev and B. N. Faddeev, Numerical Methods of Linear Algebra (in Russian). St. Petersburg, Russia: Lan, 2002.
[18] M. Fukumoto, T. Kanai, H. Kubota, and S. Tsujii, “Improvement in the stability of the BCGM-OR algorithm,” Electron. Commun. Jpn., vol. 83, no. 5, pt. 3, pp. 42-52, 2000.
[19] J. H. Husoy and M. S. E. Abadi, “A comparative study of some simplified RLS-type algorithms,” in Proc. 1st Int. Symp. Contr., Commun. Signal Process., Hammamet, Tunisia, Mar. 21-24, 2004, pp. 705-708.
[20] G. Temple, “The general theory of relaxation methods applied to linear systems,” Proc. Roy. Soc. Lond. Series A, Math. Phys. Sci., vol. 169, no. 939, pp. 476-500, 1939.
[21] J. H. Husoy, “RAMP: An adaptive filter with links to matching pursuits and iterative linear equation solvers,” in Proc. 2003 Int. Symp. Circuits Syst. (ISCAS'03), Bangkok, Thailand, May 25-28, 2003, vol. 4, pp. 381-384.
[22] Y. V. Zakharov and T. C. Tozer, “Multiplication-free iterative algorithm for LS problem,” Electron. Lett., vol. 40, no. 9, pp. 567-569, Apr. 2004.
[24] K. Dogançay and O. Tanrikulu, “Adaptive filtering algorithms with selective partial update,” IEEE Trans. Circuits Syst. II, vol. 48, no. 8, pp. 762-769, Aug. 2001.
[25] A. Bateman and I. Paterson-Stephens, The DSP Handbook: Algorithms, Applications and Design Techniques. Englewood Cliffs, NJ: Prentice-Hall, 2002.
[26] D. Boppana, K. Dhanoa, and J. Kempa, “FPGA based embedded processing architecture for the QRD-RLS algorithm,” in Proc. 12th Annu. IEEE Symp. Field-Program. Custom Computing Mach. (FCCM'04), Napa, CA, Apr. 20-23, 2004, pp. 330-331.
[27] J. Liu, Z. Quan, and Y. Zakharov, “Parallel FPGA implementation of DCD algorithm,” in Conf. DSP'2007, Cardiff, U.K., Jul. 1-4, 2007, pp. 331-334.
[28] J. Liu, B. Weaver, and G. White, “FPGA implementation of the DCD algorithm,” presented at the Commun. Symp., London, U.K., Sep. 2006.
[29] S. L. Gay and J. Benesty, Acoustic Signal Processing for Telecommunication. Norwell, MA: Kluwer Academic, 2001. Yuriy V. Zakharov (M'01) received the M.Sc. and Ph.D. degrees in electrical engineering from the Moscow Power Engineering Institute, Moscow, Russia, in 1977 and 1983, respectively. From 1977 to 1983, he was an Engineer with the Special Design Agency, Moscow Power Engineering Institute. From 1983 to 1999, he was the Head of Laboratory at the N. N. Andreev Acoustics Institute, Moscow. From 1994 to 1999, he was a DSP Group Leader with Nortel. Since 1999, he has been with the Communications Research Group, University of York, York, U.K., where he is currently a Reader. His interests include signal processing and communications. George P. White received the M.Sc. degree in digital signal processing for communications from the University of Lancaster, Lancaster, U.K., in 1997 and the Ph.D. degree in optimized turbo codes for wireless channels from the University of York, York, U.K., in 2001. From 2001 to 2007, he was with the Communications Research Group, University of York, as a Research Associate, publishing in fields such as coding and modulation, channel equalization for 3G, beamforming, high-altitude platform communications, MIMO signal processing, and modeling of amplifier nonlinearity. He is currently a Senior DSP Engineer with the Communications Division, QinetiQ, Ltd., Worcestershire, U.K.
Jie Liu received the B.S. degree in electronic science and technology from the Nanjing University, Nanjing, China, in 2004. From 2004 to 2005, he was a Wireless Product Engineer with BenQ Co., Ltd., Suzhou, China. He is currently working toward the Ph.D. degree in FPGA design for signal processing with the Department of Electronics, University of York, York, U.K. His research interests include adaptive filtering algorithms, beamforming, and hardware design.