SPECTRAL EFFECTS ON THE RATE OF CONVERGENCE OF THE LMS ADAPTIVE ALGORITHM A DISSERTATION SUBMITTED TO THE DEPARTMENT OF ELECTRICAL ENGINEERING AND THE COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Aaron E. Flores December 2005 UMI Number: 3197432 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.
Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3197432 Copyright 2006 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.
ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 © Copyright by Aarón E. Flores 2006 All Rights Reserved ii I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. Bernard Widrow Principal Adviser I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy.
Thomas Cover I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. bully Approved for the University Committee on Graduate Studies. 111 Abstract In the field of statistical signal processing, a fundamental problem is that of linearly esti- mating a random process given observations of a related random process. The usual ob- jective is to find the weights of the linear estimation that minimizes on average the square of the error.
Adaptive algorithms are used to iteratively update a weight vector, an approx- imation of the optimal solution (also called Wiener solution), as input data is presented in a streaming way. The Least Mean Square (LMS) algorithm is one of the most popular adaptive algorithms because it is simple and robust, as it is used in a wide variety of ap- plications, including digital communications, echo cancellers, system identification, GPS systems, noise canceling, antenna arrays, adaptive control, active vibration suppression systems, and many other commercial applications of significance. However, the perfor- mance of LMS may vary greatly when the autocorrelation matrix of its input has a high eigenvalue spread, so there is a need to be able to predict its performance in practice. The LMS/Newton algorithm is a variation of the LMS algorithm, it linearly pre-transforms the input so that the eigenvalues of the new input autocorrelation matrix are equal to each other.
This makes the LMS/Newton algorithm immune to the eigenvalue spread problem of LMS. However, since it requires knowledge of the input statistics often not available in practice, the LMS/Newton algorithm is mainly used as a theoretical benchmark for adap- tive algorithms. In this thesis, we study the performance of LMS relative to LMS/Newton. The performance of LMS is assessed in terms of the mean square error (MSE), and the mean square deviation (MSD) of its weight vector from the Wiener solution.
The analysis is done for stationary and nonstationary signal statistics. In the stationary case, transient behavior results when the adaptive weight vector starts from initial conditions and proceeds iv toward the Wiener solution, reaching a steady-state where the adaptive weight vector hov- ers randomly about the Wiener solution. The transient phase is thoroughly analyzed under uniform random initial conditions to evaluate how fast LMS converges to a good approx- imation of the Wiener solution. For general statistics of the initial conditions, including deterministic initial conditions as a special case, the areas under the MSE and MSD learn- ing curves are used as the convergence speed criteria.
Simple expressions are obtained for the transient performance of LMS relative to LMS/Newton’s in terms of the statistics of the input and initial conditions. In the nonstationary case, the Wiener solution varies randomly according to a random walk model, and the adapting weight vector is tracking a moving target. In this case, a steady state MSE and MSD criteria is used, obtaining simple expres- sions for the tracking performance of LMS relative to that of LMS/Newton in terms of the statistics of the input and changes of the Wiener solution. The expressions found for the stationary and nonstationary cases have a striking resemblance, showing some connections between transient and tracking behavior of the LMS and LMS/Newton algorithms.
When a transversal adaptive filter is considered, the input autocorrelation matrix is Toeplitz; this allows the expressions found for the performance of LMS to be translated into the frequency domain. Regarding the Wiener solution as an impulse response, we refer to the magnitude square of its Fourier transform as the Wiener solution spectrum. For the Transient analysis, it is found that when adapting from zero initial conditions, the ratio between the areas under the learning curves of LMS and LMS/Newton is given by the inner product of the normalized input power spectrum and Wiener solution spectrum. With our model of nonstationarity, the Wiener impulse response changes from sample time to sample time.
Take the Fourier transform of the average changes and take the magnitude square of this Fourier transform; we call this the spectrum of the Wiener solution changes. It is found that the steady state performance of LMS relative to LMS/Newton is given by the inner product of the normalized input power spectrum and spectrum of the Wiener solution changes. Our results imply that when zero initial conditions are used the transient performance of LMS is better than that of LMS/Newton, in spite of a high a eigenvalue spread, given that the input power spectrum is similar to the Wiener solution spectrum (e. a low-pass input and a low-pass Wiener filter.
In the nonstationary case, if the input spectrum is similar to the spectrum of the changes in the Wiener solution, LMS tracks better than LMS/Newton in steady-state. On the other hand, if the above spectra are dissimilar, then LMS per- forms worse than LMS/Newton, explaining the slow transient performance of LMS often observed in equalization tasks. Our results allow prediction of LMS performance in appli- cations where approximate prior knowledge of the spectra is available. This is illustrated with examples in system identification and channel equalization.
vi Acknowledgements Throughout my years at Stanford, there are a number of people who were important for the development of this thesis. First, I want to express my deepest gratitude to Prof. Bernard Widrow, who, much more than an adviser, became a friend to me. His technical expertise and strong engineering intuition, together with his patience, warmth and kind personality, have been a model for me to follow.
I am grateful to him for the invaluable experience I gained during my years by his side as a teaching assistant. He strongly supported my passion for teaching; and his drive to do research motivated by real problems, always reminded me of the ultimate goal of academic work. It was an honor and pleasure being his Ph. ) I want thank Prof.
Tom Cover for agreeing to be my associate advisor, his comments and feedback after my oral presentation were enthusiastic and motivating. I would also like to specially thank Prof. Julius Smith, for accepting to be my third reader, and for all his suggestions and enlightening discussions we had, ultimately shaping several of the chapters of this thesis. I would like to use this opportunity to express my admiration for the outstanding faculty at Stanford, in particular Profs.
Stephen Boyd, Thomas Kailath, and Robert M. Gray, who motivated and inspired my academic spirit since my first years at Stanford. I want to express my deepest gratitude to the administrative staff, specially Joice de Bolt, Marianne Marx, Diane Shankle, and Denise Murphy. They were always there for me when I needed them, and in several occasions were responsible for important and fortunate mile- stones of my path at Stanford, including my teaching experience and the many rewards that came with it.
Naturally, I thank all the Zoomates I have interacted with over the years, — past and Vil present — for the time we had together. I want to especially thank Max for all his help throughout my years in the Zoo, his tireless dedication as a sysadmin undoubtedly made the life of all his fellow Zoomates a lot easier; but more than that, I want to thank him for the many enjoyable discussions we had about technical matters, and interesting “life” topics of relevance, such as blackjack and poker. I would also like to thank Gabriel for all his help, specially for his earlier research work in Sweet Hall, which was the seed for the main ideas in this thesis. During my years at Stanford I was fortunate to have incredible friends, from both inside and outside the university.
My life as a student would have been completely different without them. They are too many to be mentioned by name, but I deeply thank them for their unconditional support in difficult times, and for all the great fun we had together over the years. I am specially grateful to my parents Ramona and Aurelio, my sister Judith, and my girlfriend Silvia, with whom my life has been blessed; thanks to their love, my experience ‘at Stanford has been a complete one. Finally, I acknowledge the financial aid from CONACYT, which helped supporting me during my first years at Stanford.
Vili Contents Abstract Acknowledgements viii 1 Introduction 1. ees +> 2 Adaptive Algorithms woOnm 2.1 Introduction to Adaptive Algorithms. Q Q HQ Q LH Ko 2.1 The steepest descentmethod.2 Derivationof the LMS algorithim.3 Convergence of the mean weight vectorforLMS. The LMS/Newton Algorthm.2 Derivation of the LMS/Newton algorithm .3 Convergence of the mean weight vector for LMS/Newton 18 2.
eee eee 21 3 Transient Analysis with Stationary Statistics 3.1 Mean Square Error (MSE) and Mean Square Deviation(MSD) .2 MSEand MSD analysisforLMS.1 Dynamics of the Weight-Error Power Vector. MSE and MSD analysis for LMS/Newton .1 Dynamics of the Weight Error Power Vector.4 Eigenvalue spread problenofLMS.5 Analysis with Random iniialcondiions. LMS Transient Efficiency 57 4. HQ HH HQ Q Q Q k kia 58 4.1 Transient Energy with random Initialcondilons.2 LMS Transient Efficiency.
LMS MSE Transient Efficiency .2 LMS MSD Transient Efficiency. 64 LMS Transient Efficiency in terms of Spectra 68 5.1 Adaptive Transversal Filter. ee ee ee 69 5. Q Q Q HQ HQ HQ ng kia 70 5.1 Continuous Fourier Spectra.
LMS Transient Efficiency in termsofSpecra .1 The R-norm and R-!-norm in the Fourierdomain .2 LMS MSE Transient Efficiency in terms of Fourier Spectra. LMS MSD Transient Efficiency in terms of Fourier Spectra 79 5. HH n Q Q Q V vn va 83 55 Applicaions. 97 Nonstationary Analysis 100 61 Nonstationarntymodel.
Ặ Q0 Q HQ eee 62 MSEandMSD AnalysisfoerLMS.1 Dynamics of the weight error power vector .2 MSE Steady state performance under Nonstationary conditions. MSD Steady state performance under Nonstationary conditions. MSE and MSD AnalysisforLMS/Newton.1 Dynamics of the weight error power vector .2 MSE Steady state performance under Nonstationary conditions. MSD Steady state performance under Nonstationary conditions .4 LMS Nonstationary Efficiency.
ee eee eee 113 6.1 LMS MSE Nonstationary Efficlency.2 LMS MSD Nonstationary Effclency. cu Q Q Q HQ HQ kg V na 120 6.5 LMS Nonstationary Efficiency in terms of Spectra.1 Fourier Spectrum of the Wiener solution steps.2 LMS MSE Nonstationary Efficiency in terms of spectra .3 LMS MSD Nonstationary Efficiency in terms of spectra. ee kia 129 7 Conclusions and Future Work 137 7. HH HH HQ kh va 137 7.