Spectral Effects on The Rate of Convergence of The LMS Adaptive Algorithm
In the field of statistical signal processing, a fundamental problem is that of linearly estimating a random process given observations of a related random process. The usual objective is to find the weights of the linear estimation that minimizes on average the square of the error. Adaptive algorit...
Lưu vào:
| Tác giả chính: | |
|---|---|
| Định dạng: | Luận án |
| Ngôn ngữ: | en_US |
| Thông tin xuất bản: |
Stanford University
2007
|
| Chủ đề: | |
| Truy cập trực tuyến: | http://ir.vnulib.edu.vn/handle/123456789/1176 |
| Từ khóa: |
Thêm từ khóa bạn đọc
Không có từ khóa, Hãy là người đầu tiên gắn từ khóa cho biểu ghi này!
|
| id |
oai:192.168.1.90:123456789-1176 |
|---|---|
| record_format |
dspace |
| institution |
Đại học Quốc Gia Hồ Chí Minh |
| collection |
DSpace |
| language |
en_US |
| topic |
Tín hiệu số, Xử lý |
| spellingShingle |
Tín hiệu số, Xử lý Flores, Aaron E. Spectral Effects on The Rate of Convergence of The LMS Adaptive Algorithm |
| description |
In the field of statistical signal processing, a fundamental problem is that of linearly estimating a random process given observations of a related random process. The usual objective 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 approximation 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 applications, 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 adaptive 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
toward the Wiener solution, reaching a steady-state where the adaptive weight vector hovers 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 approximation 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 learning 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 expressions 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.g. 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. |
| format |
Thesis |
| author |
Flores, Aaron E. |
| author_facet |
Flores, Aaron E. |
| author_sort |
Flores, Aaron E. |
| title |
Spectral Effects on The Rate of Convergence of The LMS Adaptive Algorithm |
| title_short |
Spectral Effects on The Rate of Convergence of The LMS Adaptive Algorithm |
| title_full |
Spectral Effects on The Rate of Convergence of The LMS Adaptive Algorithm |
| title_fullStr |
Spectral Effects on The Rate of Convergence of The LMS Adaptive Algorithm |
| title_full_unstemmed |
Spectral Effects on The Rate of Convergence of The LMS Adaptive Algorithm |
| title_sort |
spectral effects on the rate of convergence of the lms adaptive algorithm |
| publisher |
Stanford University |
| publishDate |
2007 |
| url |
http://ir.vnulib.edu.vn/handle/123456789/1176 |
| work_keys_str_mv |
AT floresaarone spectraleffectsontherateofconvergenceofthelmsadaptivealgorithm |
| _version_ |
1749008643034972160 |
| spelling |
oai:192.168.1.90:123456789-11762022-03-28T10:19:27Z Spectral Effects on The Rate of Convergence of The LMS Adaptive Algorithm Flores, Aaron E. Tín hiệu số, Xử lý In the field of statistical signal processing, a fundamental problem is that of linearly estimating a random process given observations of a related random process. The usual objective 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 approximation 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 applications, 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 adaptive 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 toward the Wiener solution, reaching a steady-state where the adaptive weight vector hovers 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 approximation 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 learning 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 expressions 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.g. 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. 2007-12-04T03:39:03Z 2007-12-04T03:39:03Z 2006 Thesis http://ir.vnulib.edu.vn/handle/123456789/1176 en_US Doctor of Philosophy application/pdf Stanford University |