Adaptive filters play an important role in the fields related to digital signal processing and communication, such as system identification, noise cancellation, channel equalization, and beamforming. In practical applications, the computational complexity of an adaptive filter is an important consideration. The Least Mean Square (LMS) algorithm is widely used because of its low computational complexity (O(N)) and simplicity in implementation. The least squares algorithms, such as Recursive Least Squares (RLS), Conjugate Gradient (CG), and Euclidean Direction Search (EDS), can converge faster and have lower steady-state mean square error (MSE) than LMS. However, their high computational complexity ($O(N^2)$) makes them unsuitable for many real-time applications. A well-known approach to controlling computational complexity is applying partial update (PU) method to adaptive filters. A partial update method can reduce the adaptive algorithm complexity by updating part of the weight vector instead of the entire vector or by updating part of the time. An analysis for different PU adaptive filter algorithms is necessary and meaningful. The deficient-length adaptive filter addresses a situation in system identification where the length of the estimated filter is shorter than the length of the actual unknown system. It is related to the partial update adaptive filter, but has different performance. It can be viewed as a PU adaptive filter, in that the deficient-length adaptive filter also updates part of the weight vector. However, it updates the same part of the weight vector for each iteration, while the partial update adaptive filter updates a different part of the weight vector for each iteration.
In this work, basic PU methods are applied to the adaptive filter algorithms which have not been fully addressed in the literature, including CG, EDS, and Constant Modulus Algorithm (CMA) based algorithms. A new PU method, the selective-sequential method, is developed for LSCMA. Mathematical analysis is shown including convergence condition, steady-state performance, and tracking performance. Computer simulation with proper examples is also shown to further help study the performance. The performance is compared among different PU methods or among different adaptive filtering algorithms. Computational complexity is calculated for each PU method and each adaptive filter algorithm. The deficient-length RLS and EDS are also analyzed and compared to the performance of the PU adaptive filter.
In this dissertation, basic partial-update methods are applied to adaptive filter algorithms including CMA1-2, NCMA, Least Squares CMA (LSCMA), EDS, and CG. A new PU method, the selective-sequential method, is developed for LSCMA. Mathematical derivation and performance analysis are provided including convergence condition, steady-state mean and mean-square performance for a time-invariant system. The steady-state mean and mean-square performance are also presented for a time-varying system. Computational complexity is calculated for each adaptive filter algorithm. Numerical examples are shown to compare the computational complexity of the PU adaptive filters with the full-update filters. Computer simulation examples, including system identification and channel equalization, are used to demonstrate the mathematical analysis and show the performance of PU adaptive filter algorithms. They also show the convergence performance of PU adaptive filters. The performance is compared between the original adaptive filter algorithms and different partial-update methods. The performance is also compared among similar PU least-squares adaptive filter algorithms, such as PU RLS, PU CG, and PU EDS. Deficient-length RLS and EDS are studied. The performance of the deficient-length filter is also compared with the partial update filter. In addition to the generic applications of system identification and channel equalization, two special applications of using partial update adaptive filters are also presented. One application is using PU adaptive filters to detect Global System for Mobile Communication (GSM) signals in a local GSM system using the Open Base Transceiver Station (OpenBTS) and Asterisk Private Branch Exchange (PBX). The other application is using PU adaptive filters to do image compression in a system combining hyperspectral image compression and classification.
Overall, the PU adaptive filters can usually achieve comparable performance to the full-update filters while reducing the computational complexity significantly. The PU adaptive filters can achieve similar steady-state MSE to the full-update filters. Among different PU methods, the MMax method has a convergence rate very close to the full-update method. The sequential and stochastic methods converge slower than the MMax method. However, the MMax method does not always perform well with the LSCMA algorithm. The sequential LSCMA has the best performance among the PU LSCMA algorithms. The PU CMA may perform better than the full-update CMA in tracking a time-varying system. The MMax EDS can converge faster than the MMax RLS and CG. It can converge to the same steady-state MSE as the MMax RLS and CG, while having a lower computational complexity. The PU LMS and PU EDS can also perform a little better in a system combining hyperspectral image compression and classification. / Ph. D.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/26670 |
| Date | 25 April 2012 |
| Creators | Xie, Bei |
| Contributors | Electrical and Computer Engineering, Bose, Tamal, Beex, A. A. Louis, Tranter, William H., Ha, Dong Sam, Marathe, Madhav V. |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Dissertation |
| Format | application/pdf, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | Xie_Bei_D_2011.pdf, Xie_Bei_D_2011_Copyright.pdf |
Page generated in 0.0015 seconds