Principles of adaptive filters and self-learning systems.

Contents Part I Introduction 1 1 Adaptive Filtering .............................................................................................3 1.1 Linear Adaptive Filters .............................................................................5 1.1.1 Linear Adaptive Filter Algorithms ..............................................7 1.2 Nonlinear Adaptive Filters........................................................................9 1.2.1 Adaptive Volterra Filters.............................................................9 1.3 Nonclassical Adaptive Systems ..............................................................10 1.3.1 Artificial Neural Networks ........................................................10 1.3.2 Fuzzy Logic...............................................................................11 1.3.3 Genetic Algorithms ...................................................................11 1.4 A Brief History and Overview of Classical Theories..............................12 1.4.1 Linear Estimation Theory..........................................................12 1.4.2 Linear Adaptive Filters..............................................................13 1.4.3 Adaptive Signal Processing Applications..................................14 1.4.4 Adaptive Control .......................................................................16 1.5 A Brief History and Overview of Nonclassical Theories........................17 1.5.1 Artificial Neural Networks ........................................................17 1.5.2 Fuzzy Logic...............................................................................18 1.5.3 Genetic Algorithms ...................................................................18 1.6 Fundamentals of Adaptive Networks ......................................................19 1.7 Choice of Adaptive Filter Algorithm......................................................23 2 Linear Systems and Stochastic Processes......................................................25 2.1 Basic Concepts of Linear Systems ..........................................................27 2.2 Discrete-time Signals and Systems .........................................................29 2.3 The Discrete Fourier Transform (DFT) ..................................................31 2.3.1 Discrete Linear Convolution using the DFT..............................32 2.3.2 Digital Sampling Theory ...........................................................33 2.3.2.1 Analogue Interpretation Formula...............................37 2.4 The Fast Fourier Transform....................................................................37 2.5 The z-Transform .....................................................................................40 2.5.1 Relationship between Laplace Transform and z-Transform......40 2.5.1.1 Bilateral z-Transform ................................................41 xvi Contents 2.5.1.2 Unilateral z-Transform ..............................................42 2.5.1.3 Region of Convergence (ROC) for the z-Transform .42 2.5.1.4 Region of Convergence (ROC) for General Signals..43 2.5.2 General Properties of the DFT and z-Transform.......................44 2.6 Summary of Discrete-Time LSI Systems................................................46 2.7 Special Classes of Filters ........................................................................48 2.7.1 Phase Response from Frequency Magnitude Response.............50 2.8 Linear Algebra Summary........................................................................51 2.8.1 Vectors ......................................................................................51 2.8.2 Linear Independence, Vector Spaces, and Basic Vectors..........52 2.8.3 Matrices.....................................................................................53 2.8.4 Linear Equations .......................................................................55 2.8.5 Special Matrices ........................................................................56 2.8.6 Quadratic and Hermitian Forms ................................................59 2.8.7 Eigenvalues and Eigenvectors ...................................................59 2.9 Introduction to Stochastic Processes.......................................................61 2.10 Random Signals ......................................................................................63 2.11 Basic Descriptive Models of Random Signals........................................64 2.11.1 The Mean Square Value and Variance......................................64 2.11.2 The Probability Density Function..............................................65 2.11.3 Jointly Distributed Random Variables.......................................68 2.11.4 The Expectation Operator .........................................................68 2.11.5 The Autocorrelation and Related Functions ..............................69 2.11.6 Power Spectral Density Functions.............................................72 2.11.7 Coherence Function...................................................................73 2.11.8 Discrete Ergodic Random Signal Statistics ...............................74 2.11.9 Autocovariance and Autocorrelation Matrices..........................75 2.11.10 Spectrum of a Random Process .................................................76 2.11.11 Filtering of Random Processes ..................................................78 2.11.12 Important Examples of Random Processes ...............................80 2.11.12.1 Gaussian Process .......................................................80 2.11.12.2White Noise...............................................................80 2.11.12.3White Sequences .......................................................81 2.11.12.4 Gauss-Markov Processes ...........................................81 2.11.12.5 The Random Telegraph Wave...................................81 2.12 Exercises.................................................................................................82 2.12.1 Problems....................................................................................82 Part II Modelling 87 3 Optimisation and Least Square Estimation..................................................89 3.1 Optimisation Theory ...............................................................................89 3.2 Optimisation Methods in Digital Filter Design.......................................91 3.3 Least Squares Estimation ........................................................................95 3.4 Least Squares Maximum Likelihood Estimator ......................................97 Contents xvii 3.5 Linear Regression – Fitting Data to a Line .............................................98 3.6 General Linear Least Squares .................................................................99 3.7 A Ship Positioning Example of LSE.....................................................100 3.8 Acoustic Positioning System Example..................................................104 3.9 Measure of LSE Precision ....................................................................108 3.10 Measure of LSE Reliability...................................................................109 3.11 Limitations of LSE................................................................................110 3.12 Advantages of LSE ...............................................................................110 3.13 The Singular Value Decomposition ......................................................111 3.13.1 The Pseudoinverse...................................................................112 3.13.2 Computation of the SVD.........................................................112 3.13.2.1 The Jacobi Algorithm..............................................112 3.13.2.2 The QR Algorithm...................................................115 3.14 Exercises...............................................................................................116 3.14.1 Problems..................................................................................116 4 Parametric Signal and SystemModelling ..................................................119 4.1 The Estimation Problem .......................................................................120 4.2 Deterministic Signal and System Modelling.........................................121 4.2.1 The Least Squares Method ......................................................122 4.2.2 The Padé Approximation Method ...........................................124 4.2.3 Prony’s Method .......................................................................127 4.2.3.1 All-Pole Modelling using Prony’s Method..............130 4.2.3.2 Linear Prediction .....................................................131 4.2.3.3 Digital Wiener Filter................................................132 4.2.4 Autocorrelation and Covariance Methods...............................133 4.3 Stochastic Signal Modelling ................................................................137 4.3.1 Autoregressive Moving Average Models ................................137 4.3.2 Autoregressive Models............................................................139 4.3.3 Moving Average Models.........................................................140 4.4 The Levinson-Durbin Recursion and Lattice Filters .............................141 4.4.1 The Levinson-Durbin Recursion Development .......................142 4.4.1.1 Example of the Levinson-Durbin Recursion............145 4.4.2 The Lattice Filter.....................................................................146 4.4.3 The Cholesky Decomposition .................................................149 4.4.4 The Levinson Recursion..........................................................151 4.5 Exercises...............................................................................................154 4.5.1 Problems..................................................................................154 Part III Classical Filters and Spectral Analysis 157 5 Optimum Wiener Filter ................................................................................159 5.1 Derivation of the Ideal Continuous-time Wiener Filter ........................160 5.2 The Ideal Discrete-time FIR Wiener Filter ...........................................162 5.2.1 General Noise FIR Wiener Filtering .......................................164 xviii Contents 5.2.2 FIR Wiener Linear Prediction .................................................165 5.3 Discrete-time Causal IIR Wiener Filter ................................................167 5.3.1 Causal IIR Wiener Filtering ....................................................169 5.3.2 Wiener Deconvolution ............................................................170 5.4 Exercises...............................................................................................171 5.4.1 Problems..................................................................................171 6 Optimal Kalman Filter .................................................................................173 6.1 Background to The Kalman Filter ........................................................173 6.2 The Kalman Filter.................................................................................174 6.2.1 Kalman Filter Examples ..........................................................181 6.3 Kalman Filter for Ship Motion..............................................................185 6.3.1 Kalman Tracking Filter Proper................................................186 6.3.2 Simple Example of a Dynamic Ship Models...........................189 6.3.3 Stochastic Models ...................................................................192 6.3.4 Alternate Solution Models.......................................................192 6.3.5 Advantages of Kalman Filtering..............................................193 6.3.6 Disadvantages of Kalman Filtering .........................................193 6.4 Extended Kalman Filter ........................................................................194 6.5 Exercises...............................................................................................194 6.5.1 Problems..................................................................................194 7 Power Spectral Density Analysis .................................................................197 7.1 Power Spectral Density Estimation Techniques ...................................198 7.2 Nonparametric Spectral Density Estimation .........................................199 7.2.1 Periodogram Power Spectral Density Estimation....................199 7.2.2 Modified Periodogram – Data Windowing .............................203 7.2.3 Bartlett’s Method – Periodogram Averaging ..........................205 7.2.4 Welch’s Method ......................................................................206 7.2.5 Blackman-Tukey Method........................................................208 7.2.6 Performance Comparisons of Nonparametric Models.............209 7.2.7 Minimum Variance Method ....................................................209 7.2.8 Maximum Entropy (All Poles) Method...................................212 7.3 Parametric Spectral Density Estimation................................................215 7.3.1 Autoregressive Methods..........................................................215 7.3.1.1 Yule-Walker Approach............................................216 7.3.1.2 Covariance, Least Squares and Burg Methods ........217 7.3.1.3 Model Order Selection for the Autoregressive Methods ..........................................218 7.3.2 Moving Average Method ........................................................218 7.3.3 Autoregressive Moving Average Method................................219 7.3.4 Harmonic Methods..................................................................219 7.3.4.1 Eigendecomposition of the Autocorrelation Matrix ......................................................................219 7.3.4.1.1 Pisarenko’s Method .................................221 7.3.4.1.2 MUSIC.....................................................222 Contents xix 7.4 Exercises...............................................................................................223 7.4.1 Problems..................................................................................223 Part IV Adaptive Filter Theory 225 8 Adaptive Finite Impulse Response Filters...................................................227 8.1 Adaptive Interference Cancelling .........................................................228 8.2 Least Mean Squares Adaptation ...........................................................230 8.2.1 OptimumWiener Solution.......................................................231 8.2.2 The Method of Steepest Gradient Descent Solution................233 8.2.3 The LMS Algorithm Solution..................................................235 8.2.4 Stability of the LMS Algorithm...............................................237 8.2.5 The Normalised LMS Algorithm.............................................239 8.3 Recursive Least Squares Estimation .....................................................239 8.3.1 The ExponentiallyWeighted Recursive Least Squares Algorithm...................................................................240 8.3.2 Recursive Least Squares Algorithm Convergence...................243 8.3.2.1 Convergence of the Filter Coefficients in the Mean..................................................................243 8.3.2.2 Convergence of the Filter Coefficients in the Mean Square ......................................................244 8.3.2.3 Convergence of the RLS Algorithm in the Mean Square ......................................................244 8.3.3 The RLS Algorithm as a Kalman Filter...................................244 8.4 Exercises...............................................................................................245 8.4.1 Problems..................................................................................245 9 Frequency Domain Adaptive Filters ...........................................................247 9.1 Frequency Domain Processing..............................................................247 9.1.1 Time Domain Block Adaptive Filtering ..................................248 9.1.2 Frequency Domain Adaptive Filtering ....................................249 9.1.2.1 The Overlap-Save Method.......................................251 9.1.2.2 The Overlap-Add Method .......................................254 9.1.2.3 The Circular Convolution Method...........................255 9.1.2.4 Computational Complexity......................................256 9.2 Exercises...............................................................................................256 9.2.1 Problems..................................................................................256 10 Adaptive Volterra Filters .............................................................................257 10.1 Nonlinear Filters ...................................................................................257 10.2 The Volterra Series Expansion .............................................................259 10.3 A LMS Adaptive Second-order Volterra Filter ....................................259 10.4 A LMS Adaptive Quadratic Filter ........................................................261 10.5 A RLS Adaptive Quadratic Filter .........................................................262 10.6 Exercises...............................................................................................264 xx Contents 10.6.1 Problems..................................................................................264 11 Adaptive Control Systems ............................................................................267 11.1 Main Theoretical Issues ........................................................................268 11.2 Introduction to Model-reference Adaptive Systems..............................270 11.2.1 The Gradient Approach...........................................................271 11.2.2 Least Squares Estimation ........................................................273 11.2.3 A General Single-input-single-output MRAS..........................274 11.2.4 Lyapunov’s Stability Theory ...................................................277 11.3 Introduction to Self-tuning Regulators..................................................280 11.3.1 Indirect Self-tuning Regulators................................................282 11.3.2 Direct Self-tuning Regulators ..................................................283 11.4 Relations between MRAS and STR......................................................284 11.5 Applications..........................................................................................285 Part V Nonclassical Adaptive Systems 287 12 Introduction to Neural Networks ................................................................289 12.1 Artificial Neural Networks....................................................................289 12.1.1 Definitions...............................................................................290 12.1.2 Three Main Types ...................................................................290 12.1.3 Specific Artificial Neural Network Paradigms ........................292 12.1.4 Artificial Neural Networks as Black Boxed ............................293 12.1.5 Implementation of Artificial Neural Networks........................294 12.1.6 When to Use an Artificial Neural Network .............................295 12.1.7 How to Use an Artificial Neural Network ...............................295 12.1.8 Artificial Neural Network General Applications.....................296 12.1.9 Simple Application Examples .................................................297 12.1.9.1 Sheep Eating Phase Identification from Jaw Sounds .....................................................................298 12.1.9.2 Hydrate Particle Isolation in SEM Images...............298 12.1.9.3 Oxalate Needle Detection in Microscope Images....299 12.1.9.4 Water Level Determination from Resonant Sound Analysis ........................................................299 12.1.9.5 Nonlinear Signal Filtering .......................................299 12.1.9.6 A Motor Control Example .......................................300 12.2 A Three-layer Multi-layer Perceptron Model .......................................300 12.2.1 MLP Backpropagation-of-error Learning................................302 12.2.2 Derivation of Backpropagation-of-error Learning ..................303 12.2.2.1 Change in Error due to Output Layer Weights ........303 12.2.2.2 Change in Error due to Hidden Layer Weights........304 12.2.2.3 The Weight Adjustments .........................................305 12.2.2.4 Additional Momentum Factor .................................307 12.2.3 Notes on Classification and Function Mapping.......................308 12.2.4 MLP Application and Training Issues.....................................308 Contents xxi 12.3 Exercises...............................................................................................310 12.3.1 Problems..................................................................................310 13 Introduction to Fuzzy Logic Systems ..........................................................313 13.1 Basic Fuzzy Logic ................................................................................313 13.1.1 Fuzzy Logic Membership Functions .......................................314 13.1.2 Fuzzy Logic Operations ..........................................................315 13.1.3 Fuzzy Logic Rules...................................................................316 13.1.4 Fuzzy Logic Defuzzification ...................................................317 13.2 Fuzzy Logic Control Design .................................................................318 13.2.1 Fuzzy Logic Controllers ..........................................................319 13.2.1.1 Control Rule Construction.......................................319 13.2.1.2 Parameter Tuning ....................................................321 13.2.1.3 Control Rule Revision .............................................322 13.3 Fuzzy Artificial Neural Networks .........................................................322 13.4 Fuzzy Applications ...............................................................................323 14 Introduction to Genetic Algorithms ............................................................325 14.1 A General Genetic Algorithm...............................................................326 14.2 The Common Hypothesis Representation.............................................327 14.3 Genetic Algorithm Operators................................................................329 14.4 Fitness Functions ..................................................................................330 14.5 Hypothesis Searching............................................................................330 14.6 Genetic Programming ...........................................................................331 14.7 Applications of Genetic Programming..................................................332 14.7.1 Filter Circuit Design Applications of GAs and GP .................333 14.7.2 Tic-tac-to Game Playing Application of GAs .........................334 Part VI Adaptive Filter Application 337 15 Applications of Adaptive Signal Processing ...............................................339 15.1 Adaptive Prediction ..............................................................................340 15.2 Adaptive Modelling ..............................................................................342 15.3 Adaptive Telephone Echo Cancelling...................................................343 15.4 Adaptive Equalisation of Communication Channels.............................344 15.5 Adaptive Self-tuning Filters..................................................................346 15.6 Adaptive Noise Cancelling ...................................................................346 15.7 Focused Time Delay Estimation for Ranging .......................................348 15.7.1 Adaptive Array Processing......................................................349 15.8 Other Adaptive Filter Applications.......................................................350 15.8.1 Adaptive 3-D Sound Systems..................................................350 15.8.2 Microphone Arrays..................................................................351 15.8.3 Network and Acoustic Echo Cancellation ...............................352 15.8.4 Real-world Adaptive Filtering Applications............................353 xxii Contents 16 Generic Adaptive Filter Structures.............................................................355 16.1 Sub-band Adaptive Filters ....................................................................355 16.2 Sub-space Adaptive Filters ...................................................................358 16.2.1 MPNN Model..........................................................................360 16.2.2 Approximately Piecewise Linear Regression Model...............362 16.2.3 The Sub-space Adaptive Filter Model.....................................364 16.2.4 Example Applications of the SSAF Model..............................366 16.2.4.1 Loudspeaker 3-D Frequency Response Model ........367 16.2.4.2 Velocity of Sound in Water 3-D Model...................369 16.3 Discussion and Overview of the SSAF .................................................370 References ...........................................................................................................373 Index ....................................................................................................................381