Fundamentals of Adaptive Filtering

PREFACE xix

ACKNOWLEDGMENTS xxix

NOTATION xxxi

SYMBOLS xxxv

1 OPTIMAL ESTIMATION 1

1.1 Variance of a Random Variable 1

1.2 Estimation Given No Observations 5

1.3 Estimation Given Dependent Observations 6

1.4 Estimation in the Complex and Vector Cases 18

1.5 Summary of Main Results 30

1.6 Bibliographic Notes 31

1.7 Problems 33

1.8 Computer Project 37

l.A Hermitian and Positive-Definite Matrices 39

l.B Gaussian Random Vectors 42

2 LINEAR ESTIMATION 47

2.1 Normal Equations 48

2.2 Design Examples 54

2.3 Existence of Solutions 60

2.4 Orthogonality Principle 63

2.5 Nonzero-Mean Variables 65

2.6 Linear Models 66

2.7 Applications 68

2.8 Summary of Main Results 76

2.9 Bibliographic Notes 77

2.10 Problems 79

2.11 Computer Project 95

2.A Range Spaces and Nullspaces of Matrices 103

2.B Complex Gradients 105

2.C Kalman Filter 108

3 CONSTRAINED LINEAR ESTIMATION 114

3.1 Minimum-Variance Unbiased Estimation 115

3.2 Application: Channel and Noise Estimation 119

3.3 Application: Decision Feedback Equalization 120

3.4 Application: Antenna Beamforming 128

3.5 Summary of Main Results 131

3.6 Bibliographic Notes 131

3.7 Problems 133

3.8 Two Computer Projects 143

3.A Schur Complements 155

3.B Primer on Channel Equalization 159

3.C Causal Wiener-Hopf Filtering 167

4 STEEPEST-DESCENT ALGORITHMS 170

4.1 Linear Estimation Problem 171

4.2 Steepest-Descent Method 174

4.3 Transient Behavior 179

4.4 Iteration-Dependent Step-Sizes 187

4.5 Newton's Method 191

4.6 Summary of Main Results 193

4.7 Bibliographic Notes 194

4.8 Problems 196

4.9 Two Computer Projects 204

5 STOCHASTIC-GRADIENT ALGORITHMS 212

5.1 Motivation 213

5.2 LMS Algorithm 214

5.3 Application: Adaptive Channel Estimation 218

5.4 Application: Adaptive Channel Equalization 220

5.5 Application: Decision-Feedback Equalization 223

5.6 Normalized LMS Algorithm 225

5.7 Other LMS-type Algorithms 233

5.8 Affine Projection Algorithms 238

5.9 RLS Algorithm 245

5.10 Ensemble-Average Learning Curves 248

5.11 Summary of Main Results 251

5.12 Bibliographic Notes 252

5.13 Problems 256

5.14 Three Computer Projects 267

6 STEADY-STATE PERFORMANCE OF ADAPTIVE FILTERS 281

6.1 Performance Measure 282

6.2 Stationary Data Model 284

6.3 Fundamental Energy-Conservation Relation 287

6.4 Fundamental Variance Relation 290

6.5 Mean-Square Performance of LMS 292

6.6 Mean-Square Performance of €-NLMS 300

6.7 Mean-Square Performance of Sign-Error LMS 305

6.S Mean-Square Performance of LMF and LMMN 308

6.9 Mean-Square Performance of RLS 317

6.10 Mean-Square Performance of e-APA 322

6.11 Mean-Square Performance of Other Filters 325

6.12 Performance Table for Small Step-Sizes 327

6.13 Summary of Main Results 327

6.14 Bibliographic Notes 329

6.15 Problems 332

6.16 Computer Project 343

6.A Interpretations of the Energy Relation 348

6.B Relating e-NLMS to LMS 353

6.C Affine Projection Performance Condition 355

7 TRACKING PERFORMANCE OF ADAPTIVE FILTERS 357

7.1 Motivation 357

7.2 Nonstationary Data Model 358

7.3 Fundamental Energy-Conservation Relation 364

7.4 Fundamental Variance Relation 364

7.5 Tracking Performance of LMS 367

7.6 Tracking Performance of e-NLMS 370

7.7 Tracking Performance of Sign-Error LMS 372

7.8 Tracking Performance of LMF and LMMN 374

7.9 Comparison of Tracking Performance 378

7.10 Tracking Performance of RLS 380

7.11 Tracking Performance of e-APA 384

7.12 Tracking Performance of Other Filters 386

7.13 Performance Table for Small Step-Sizes 387

7.14 Summary of Main Results 387

7.15 Bibliographic Notes 389

7.16 Problems 391

7.17 Computer Project 401

8 FINITE PRECISION EFFECTS 408

8.1 Quantization Model 409

8.2 Data Model and Quantization Error Sources 410

8.3 Fundamental Energy-Conservation Relation 413

8.4 Fundamental Variance Relation 416

8.5 Performance Degradation of LMS 419

8.6 Performance Degradation of e-NLMS 421

8.7 Performance Degradation of Sign-Error LMS 423

8.8 Performance Degradation of LMF and LMMN 424

8.9 Performance Degradation of Other Filters 425

8.10 Summary of Main Results 426

8.11 Bibliographic Notes 428

8.12 Problems 430

8.13 Computer Project 437

9 TRANSIENT PERFORMANCE OF ADAPTIVE FILTERS 441

9.1 Data Model 442

9.2 Data-Normalized Adaptive Filters 442

9.3 Weighted Energy-Conservation Relation 443

9.4 Weighted Variance Relation 445

9.5 Transient Performance of LMS 452

9.6 Transient Performance of e-NLMS 471

9.7 Performance of Data-Normalized Filters 474

9.8 Summary of Main Results 477

9.9 Bibliographic Notes 481

9.10 Problems 487

9.11 Computer Project 516

9.A Stability Bound 522

9.B Stability of e-NLMS 524

9.C Adaptive Filters with Error Nonlinearities 526

9.D Convergence Time of Adaptive Filters 538

9.E Learning Behavior of Adaptive Filters 545

9.F Independence and Averaging Analysis 559

9.G Interpretation of Weighted Energy Relation 568

9.H Kronecker Products 570

10 BLOCK ADAPTIVE FILTERS 572

10.1 Transform-Domain Adaptive Filters 573

10.2 Motivation for Block Adaptive Filters 584

10.3 Efficient Block Convolution 586

10.4 DFT-Based Block Adaptive Filters 597

10.5 Subband Adaptive Filters 605

10.6 Summary of Main Results 612

10.7 Bibliographic Notes 614

10.8 Problems 616

10.9 Computer Project 620

10.A DCT-Transformed Regressors 626

10.B More Constrained DFT Block Filters 628

10.C Overlap-Add DFT-Based Block Adaptive Filter 632

10.D DCT-Based Block Adaptive Filters 640

10.E DHT-Based Block Adaptive Filters 648

11 THE LEAST-SQUARES CRITERION 657

11.1 Least-Squares Problem 658

11.2 Weighted Least-Squares 666

11.3 Regularized Least-Squares 669

11.4 Weighted Regularized Least-Squares 671

11.5 Order-Update Relations 672

11.6 Summary of Main Results 688

11.7 Bibliographic Notes 689

11.8 Problems 693

11.9 Three Computer Projects 703

11.A Equivalence Results in Linear Estimation 724

ll.B QR Decomposition 726

ll.C Singular Value Decomposition 728

12 RECURSIVE LEAST-SQUARES 732

12.1 Motivation 732

12.2 RLS Algorithm 733

12.3 Exponentially-Weighted RLS Algorithm 739

12.4 General Time-Update Result 741

12.5 Summary of Main Results 745

12.6 Bibliographic Notes 745

12.7 Problems 748

12.8 Two Computer Projects 755

12.A Kalman Filtering and Recursive Least-Squares 763

12.B Extended RLS Algorithms 768

13 RLS ARRAY ALGORITHMS 775

13.1 Some Difficulties 775

13.2 Square-Root Factors 776

13.3 Norm and Angle Preservation 778

13.4 Motivation for Array Methods 780

13.5 RLS Algorithm 784

13.6 Inverse QR Algorithm 785

13.7 QR Algorithm 788

13.8 Extended QR Algorithm 793

13.9 Summary of Main Results 794

13.10 Bibliographic Notes 795

13.11 Problems 797

13.12 Computer Project 802

13.A Unitary Transformations 804

13.A.I Givens Rotations 804

13.A.2 Householder Transformations 808

13.B Array Algorithms for Kalman Filtering 812

14 FAST FIXED-ORDER FILTERS 816

14.1 Fast Array Algorithm 817

14.2 Regularized Prediction Problems 825

14.3 Fast Transversal Filter 832

14.4 FAEST Filter 836

14.5 Fast Kalman Filter 838

14.6 Stability Issues 839

14.7 Summary of Main Results 845

14.8 Bibliographic Notes 846

14.9 Problems 848

14.10 Computer Project 857

14.A Hyperbolic Rotations 860

14.B Hyperbolic Basis Rotations 867

14.C Backward Consistency and Minimality 869

14.D Chandrasekhar Filter 871

15 LATTICE FILTERS 874

15.1 Motivation and Notation 875

15.2 Joint Process Estimation 878

15.3 Backward Estimation Problem 880

15.4 Forward Estimation Problem 883

15.5 Time and Order-Update Relations 885

15.6 Significance of Data Structure 891

15.7 A Posteriori-Based Lattice Filter 894

15.8 A Priori-Based Lattice Filter 895

15.9 A Priori Error-Feedback Lattice Filter 897

15.10 A Posteriori Error-Feedback Lattice Filter 902

15.11 Normalized Lattice Filter 904

15.12 Array-Based Lattice Filter 910

15.13 Relation Between RLS and Lattice Filters 915

15.14 Summary of Main Results 917

15.15 Bibliographic Notes 918

15.16 Problems 920

15.17 Computer Project 925

16 LAGUERRE ADAPTIVE FILTERS 931

16.1 Orthonormal Filter Structures 932

16.2 Data Structure 934

16.3 Fast Array Algorithm 936

16.4 Regularized Projection Problems 942

16.5 Extended Fast Transversal Filter 954

16.6 Extended FAEST Filter 957

16.7 Extended Fast Kalman Filter 958

16.8 Stability Issues 959

16.9 Order-Recursive Filters 960

16.10 A Posteriori-Based Lattice Filter 968

16.11 A Priori-Based Lattice Filter 970

16.12 A Priori Error-Feedback Lattice Filter 972

16.13 A Posteriori Error-Feedback Lattice Filter 976

16.14 Normalized Lattice Filter 978

16.15 Array Lattice Filter 982

16.16 Summary of Main Results 985

16.17 Bibliographic Notes 986

16.18 Problems 989

16.19 Computer Project 994

16.A Modeling with Orthonormal Basis Functions 999

16.B Efficient Matrix-Vector Multiplication 1007

16.C Lyapunov Equations 1009

17 ROBUST ADAPTIVE FILTERS 1012

17.1 Indefinite Least-Squares 1013

17.2 Recursive Minimization Algorithm 1018

17.3 A Posteriori-Based Robust Filters 1027

17.4 A Priori-Based Robust Filters 1036

17.5 Energy Conservation Arguments 1043

17.6 Summary of Main Results 1052

17.7 Bibliographic Notes 1052

17.8 Problems 1056

17.9 Computer Project 1072

17.A Arbitrary Coefficient Matrices 1078

17.B Total-Least-Squares 1081

17.C H°° Filters 1085

17.D Stationary Points 1089

BIBLIOGRAPHY 1090

AUTHOR INDEX 1113

SUBJECT INDEX 1118