Fundamentals of Adaptive Filtering

ALI H. SAYED, PhD, is a professor of electrical engineering at UCLA, where he established and directs the Adaptive Systems Laboratory. He is a Fellow of the IEEE for his contributions to adaptive filtering and estimation algorithms.

"...a remarkably clear, accessible, and up-to-date text. It is highly recommended for students at the graduate level…is an invaluable and comprehensive reference…for researchers at all levels." (IEEE Control Systems Magazine, August 2005)

• PREFACE xixACKNOWLEDGMENTS xxixNOTATION xxxiSYMBOLS xxxv1 OPTIMAL ESTIMATION 11.1 Variance of a Random Variable 11.2 Estimation Given No Observations 51.3 Estimation Given Dependent Observations 61.4 Estimation in the Complex and Vector Cases 181.5 Summary of Main Results 301.6 Bibliographic Notes 311.7 Problems 331.8 Computer Project 37l.A Hermitian and Positive-Definite Matrices 39l.B Gaussian Random Vectors 422 LINEAR ESTIMATION 472.1 Normal Equations 482.2 Design Examples 542.3 Existence of Solutions 602.4 Orthogonality Principle 632.5 Nonzero-Mean Variables 652.6 Linear Models 662.7 Applications 682.8 Summary of Main Results 762.9 Bibliographic Notes 772.10 Problems 792.11 Computer Project 952.A Range Spaces and Nullspaces of Matrices 1032.B Complex Gradients 1052.C Kalman Filter 1083 CONSTRAINED LINEAR ESTIMATION 1143.1 Minimum-Variance Unbiased Estimation 1153.2 Application: Channel and Noise Estimation 1193.3 Application: Decision Feedback Equalization 1203.4 Application: Antenna Beamforming 1283.5 Summary of Main Results 1313.6 Bibliographic Notes 1313.7 Problems 1333.8 Two Computer Projects 1433.A Schur Complements 1553.B Primer on Channel Equalization 1593.C Causal Wiener-Hopf Filtering 1674 STEEPEST-DESCENT ALGORITHMS 1704.1 Linear Estimation Problem 1714.2 Steepest-Descent Method 1744.3 Transient Behavior 1794.4 Iteration-Dependent Step-Sizes 1874.5 Newton's Method 1914.6 Summary of Main Results 1934.7 Bibliographic Notes 1944.8 Problems 1964.9 Two Computer Projects 2045 STOCHASTIC-GRADIENT ALGORITHMS 2125.1 Motivation 2135.2 LMS Algorithm 2145.3 Application: Adaptive Channel Estimation 2185.4 Application: Adaptive Channel Equalization 2205.5 Application: Decision-Feedback Equalization 2235.6 Normalized LMS Algorithm 2255.7 Other LMS-type Algorithms 2335.8 Affine Projection Algorithms 2385.9 RLS Algorithm 2455.10 Ensemble-Average Learning Curves 2485.11 Summary of Main Results 2515.12 Bibliographic Notes 2525.13 Problems 2565.14 Three Computer Projects 2676 STEADY-STATE PERFORMANCE OF ADAPTIVE FILTERS 2816.1 Performance Measure 2826.2 Stationary Data Model 2846.3 Fundamental Energy-Conservation Relation 2876.4 Fundamental Variance Relation 2906.5 Mean-Square Performance of LMS 2926.6 Mean-Square Performance of €-NLMS 3006.7 Mean-Square Performance of Sign-Error LMS 3056.S Mean-Square Performance of LMF and LMMN 3086.9 Mean-Square Performance of RLS 3176.10 Mean-Square Performance of e-APA 3226.11 Mean-Square Performance of Other Filters 3256.12 Performance Table for Small Step-Sizes 3276.13 Summary of Main Results 3276.14 Bibliographic Notes 3296.15 Problems 3326.16 Computer Project 3436.A Interpretations of the Energy Relation 3486.B Relating e-NLMS to LMS 3536.C Affine Projection Performance Condition 3557 TRACKING PERFORMANCE OF ADAPTIVE FILTERS 3577.1 Motivation 3577.2 Nonstationary Data Model 3587.3 Fundamental Energy-Conservation Relation 3647.4 Fundamental Variance Relation 3647.5 Tracking Performance of LMS 3677.6 Tracking Performance of e-NLMS 3707.7 Tracking Performance of Sign-Error LMS 3727.8 Tracking Performance of LMF and LMMN 3747.9 Comparison of Tracking Performance 3787.10 Tracking Performance of RLS 3807.11 Tracking Performance of e-APA 3847.12 Tracking Performance of Other Filters 3867.13 Performance Table for Small Step-Sizes 3877.14 Summary of Main Results 3877.15 Bibliographic Notes 3897.16 Problems 3917.17 Computer Project 4018 FINITE PRECISION EFFECTS 4088.1 Quantization Model 4098.2 Data Model and Quantization Error Sources 4108.3 Fundamental Energy-Conservation Relation 4138.4 Fundamental Variance Relation 4168.5 Performance Degradation of LMS 4198.6 Performance Degradation of e-NLMS 4218.7 Performance Degradation of Sign-Error LMS 4238.8 Performance Degradation of LMF and LMMN 4248.9 Performance Degradation of Other Filters 4258.10 Summary of Main Results 4268.11 Bibliographic Notes 4288.12 Problems 4308.13 Computer Project 4379 TRANSIENT PERFORMANCE OF ADAPTIVE FILTERS 4419.1 Data Model 4429.2 Data-Normalized Adaptive Filters 4429.3 Weighted Energy-Conservation Relation 4439.4 Weighted Variance Relation 4459.5 Transient Performance of LMS 4529.6 Transient Performance of e-NLMS 4719.7 Performance of Data-Normalized Filters 4749.8 Summary of Main Results 4779.9 Bibliographic Notes 4819.10 Problems 4879.11 Computer Project 5169.A Stability Bound 5229.B Stability of e-NLMS 5249.C Adaptive Filters with Error Nonlinearities 5269.D Convergence Time of Adaptive Filters 5389.E Learning Behavior of Adaptive Filters 5459.F Independence and Averaging Analysis 5599.G Interpretation of Weighted Energy Relation 5689.H Kronecker Products 57010 BLOCK ADAPTIVE FILTERS 57210.1 Transform-Domain Adaptive Filters 57310.2 Motivation for Block Adaptive Filters 58410.3 Efficient Block Convolution 58610.4 DFT-Based Block Adaptive Filters 59710.5 Subband Adaptive Filters 60510.6 Summary of Main Results 61210.7 Bibliographic Notes 61410.8 Problems 61610.9 Computer Project 62010.A DCT-Transformed Regressors 62610.B More Constrained DFT Block Filters 62810.C Overlap-Add DFT-Based Block Adaptive Filter 63210.D DCT-Based Block Adaptive Filters 64010.E DHT-Based Block Adaptive Filters 64811 THE LEAST-SQUARES CRITERION 65711.1 Least-Squares Problem 65811.2 Weighted Least-Squares 66611.3 Regularized Least-Squares 66911.4 Weighted Regularized Least-Squares 67111.5 Order-Update Relations 67211.6 Summary of Main Results 68811.7 Bibliographic Notes 68911.8 Problems 69311.9 Three Computer Projects 70311.A Equivalence Results in Linear Estimation 724ll.B QR Decomposition 726ll.C Singular Value Decomposition 72812 RECURSIVE LEAST-SQUARES 73212.1 Motivation 73212.2 RLS Algorithm 73312.3 Exponentially-Weighted RLS Algorithm 73912.4 General Time-Update Result 74112.5 Summary of Main Results 74512.6 Bibliographic Notes 74512.7 Problems 74812.8 Two Computer Projects 75512.A Kalman Filtering and Recursive Least-Squares 76312.B Extended RLS Algorithms 76813 RLS ARRAY ALGORITHMS 77513.1 Some Difficulties 77513.2 Square-Root Factors 77613.3 Norm and Angle Preservation 77813.4 Motivation for Array Methods 78013.5 RLS Algorithm 78413.6 Inverse QR Algorithm 78513.7 QR Algorithm 78813.8 Extended QR Algorithm 79313.9 Summary of Main Results 79413.10 Bibliographic Notes 79513.11 Problems 79713.12 Computer Project 80213.A Unitary Transformations 80413.A.I Givens Rotations 80413.A.2 Householder Transformations 80813.B Array Algorithms for Kalman Filtering 81214 FAST FIXED-ORDER FILTERS 81614.1 Fast Array Algorithm 81714.2 Regularized Prediction Problems 82514.3 Fast Transversal Filter 83214.4 FAEST Filter 83614.5 Fast Kalman Filter 83814.6 Stability Issues 83914.7 Summary of Main Results 84514.8 Bibliographic Notes 84614.9 Problems 84814.10 Computer Project 85714.A Hyperbolic Rotations 86014.B Hyperbolic Basis Rotations 86714.C Backward Consistency and Minimality 86914.D Chandrasekhar Filter 87115 LATTICE FILTERS 87415.1 Motivation and Notation 87515.2 Joint Process Estimation 87815.3 Backward Estimation Problem 88015.4 Forward Estimation Problem 88315.5 Time and Order-Update Relations 88515.6 Significance of Data Structure 89115.7 A Posteriori-Based Lattice Filter 89415.8 A Priori-Based Lattice Filter 89515.9 A Priori Error-Feedback Lattice Filter 89715.10 A Posteriori Error-Feedback Lattice Filter 90215.11 Normalized Lattice Filter 90415.12 Array-Based Lattice Filter 91015.13 Relation Between RLS and Lattice Filters 91515.14 Summary of Main Results 91715.15 Bibliographic Notes 91815.16 Problems 92015.17 Computer Project 92516 LAGUERRE ADAPTIVE FILTERS 93116.1 Orthonormal Filter Structures 93216.2 Data Structure 93416.3 Fast Array Algorithm 93616.4 Regularized Projection Problems 94216.5 Extended Fast Transversal Filter 95416.6 Extended FAEST Filter 95716.7 Extended Fast Kalman Filter 95816.8 Stability Issues 95916.9 Order-Recursive Filters 96016.10 A Posteriori-Based Lattice Filter 96816.11 A Priori-Based Lattice Filter 97016.12 A Priori Error-Feedback Lattice Filter 97216.13 A Posteriori Error-Feedback Lattice Filter 97616.14 Normalized Lattice Filter 97816.15 Array Lattice Filter 98216.16 Summary of Main Results 98516.17 Bibliographic Notes 98616.18 Problems 98916.19 Computer Project 99416.A Modeling with Orthonormal Basis Functions 99916.B Efficient Matrix-Vector Multiplication 100716.C Lyapunov Equations 100917 ROBUST ADAPTIVE FILTERS 101217.1 Indefinite Least-Squares 101317.2 Recursive Minimization Algorithm 101817.3 A Posteriori-Based Robust Filters 102717.4 A Priori-Based Robust Filters 103617.5 Energy Conservation Arguments 104317.6 Summary of Main Results 105217.7 Bibliographic Notes 105217.8 Problems 105617.9 Computer Project 107217.A Arbitrary Coefficient Matrices 107817.B Total-Least-Squares 108117.C H°° Filters 108517.D Stationary Points 1089BIBLIOGRAPHY 1090AUTHOR INDEX 1113SUBJECT INDEX 1118