QRD-RLS Adaptive Filtering (eBook)

Foreword 6
Preface 8
Contents 10
List of Contributors 16
1 QR Decomposition: An Annotated Bibliography 19
Marcello L. R. de Campos and Gilbert Strang 19
Preamble 19
Eigenvalues and Eigenvectors 20
Iterative Methods for the Solution of the Eigenproblem 21
The LR algorithm 21
The QR algorithm 22
QR Decomposition for Orthogonalization 23
The classical Gram--Schmidt orthogonalizationmethod 24
The modified Gram--Schmidt orthogonalizationmethod 26
Triangularization via Householder reflections 27
Triangularization via Givens plane rotations 28
QR Decomposition for Linear Least Squares Problems 30
QR Decomposition by systolic arrays 32
QR Decomposition for Recursive Least Squares AdaptiveFilters 32
Fast QR decomposition RLS adaptation algorithms 34
Conclusion 35
References 36
2 Introduction to Adaptive Filters 41
José A. Apolinário Jr. and Sergio L. Netto 41
Basic Concepts 41
Error Measurements 46
The mean-square error 46
The instantaneous square error 47
The weighted least-squares 47
Adaptation Algorithms 48
LMS and normalized-LMS algorithms 49
Data-reusing LMS algorithms 52
RLS-type algorithms 58
Computer Simulations 60
Example 1: Misadjustment of the LMS algorithm 60
Example 2: Convergence trajectories 61
Example 3: Tracking performance 61
Example 4: Algorithm stability 64
Conclusion 65
References 66
3 Conventional and Inverse QRD-RLS Algorithms 68
José A. Apolinário Jr. and Maria D. Miranda 68
The Least-Squares Problem and the QR Decomposition 68
The Givens Rotation Method 74
The Conventional QRD-RLS Algorithm 77
Initialization of the Triangularization Procedure 81
On the Q(k) Matrix 83
The backward prediction problem 86
The forward prediction problem 88
Interpreting the elements of Q(k) for a lower triangular Cholesky factor 91
Interpreting the elements of Q(k) for an upper triangular Cholesky factor 92
The Inverse QRD-RLS Algorithm 93
Conclusion 94
Appendix 1 96
Appendix 2 97
Appendix 3 98
References 101
4 Fast QRD-RLS Algorithms 103
José A. Apolinário Jr. and Paulo S. R. Diniz 103
Introduction 103
Upper Triangularization Algorithms (Updating Forward Prediction Errors) 105
The FQR_POS_F algorithm 106
The FQR_PRI_F algorithm 108
Lower Triangularization Algorithms (Updating Backward Prediction Errors) 109
The FQR_POS_B algorithm 111
The FQR_PRI_B algorithm 114
The Order Recursive Versions of the Fast QRD Algorithms 116
Conclusion 120
Appendix 1 121
Appendix 2 123
Appendix 3 127
References 129
5 QRD Least-Squares Lattice Algorithms 130
Jenq-Tay Yuan 130
Fundamentals of QRD-LSL Algorithms 131
LSL Interpolator and LSL Predictor 133
LSL interpolator 134
Orthogonal bases for LSL interpolator 136
LSL predictor 137
SRF Givens Rotation with Feedback Mechanism 138
SRF QRD-LSL Algorithms 140
QRD based on interpolation 141
SRF QRD-LSL interpolation algorithm 144
SRF QRD-LSL prediction algorithm and SRF joint process estimation 151
SRF (QRD-LSL)-Based RLS Algorithm 154
Simulations 155
Conclusion 157
References 158
6 Multichannel Fast QRD-RLS Algorithms 161
António L. L. Ramos and Stefan Werner 161
Introduction 161
Problem Formulation 163
Redefining the input vector 165
Input vector for sequential-type multichannelalgorithms 166
Input vector for block-type multichannel algorithms 167
Sequential-Type MC-FQRD-RLS Algorithms 167
Triangularization of the information matrix 168
A priori and A posteriori versions 171
Alternative implementations 173
Block-Type MC-FQRD-RLS Algorithms 176
The backward and forward prediction problems 176
A priori and A posteriori versions 180
Alternative implementations 183
Order-Recursive MC-FQRD-RLS Algorithms 185
Application Example and Computational Complexity Issues 190
Application example 190
Computational complexity issues 192
Conclusion 193
References 193
7 Householder-Based RLS Algorithms 195
Athanasios A. Rontogiannis and Sergios Theodoridis 195
Householder Transforms 195
Hyperbolic Householder transforms 198
Row Householder transforms 198
The Householder RLS (HRLS) Algorithm 200
Applications 204
The Householder Block Exact QRD-RLS Algorithm 206
The Householder Block Exact Inverse QRD-RLS Algorithm 210
Sliding Window (SW) Householder Block Implementation 213
Conclusion 216
References 216
8 Numerical Stability Properties 218
Phillip Regalia and Richard Le Borne 218
Introduction 218
Preliminaries 219
Conditioning, forward stability, and backwardstability 221
The Conditioning of the Least-Squares Problem 223
The conditioning of the least-squares problem 224
Consistency, stability, and convergence 225
The Recursive QR Least-Squares Methods 227
Full QR decomposition adaptive algorithm 227
Fast QR Algorithms 233
Past input reconstruction 236
Reachable states in fast least-squares algorithms 240
QR decomposition lattice algorithm 242
Conclusion 244
References 245
9 Finite and Infinite-Precision Properties of QRD-RLS Algorithms 247
Paulo S. R. Diniz and Marcio G. Siqueira 247
Introduction 247
Precision Analysis of the QR-Decomposition RLS Algorithm 248
Infinite-precision analysis 249
Stability analysis 254
Error propagation analysis in steady-state 256
Simulation results 267
Precision Analysis of the Fast QRD-Lattice Algorithm 268
Infinite-precision analysis 270
Finite-precision analysis 273
Simulation results 277
Conclusion 278
References 278
10 On Pipelined Implementations of QRD-RLS Adaptive Filters 280
Jun Ma and Keshab K. Parhi 280
QRD-RLS Systolic Architecture 281
The Annihilation-Reording Look-Ahead Technique 284
Look-ahead through block processing 285
Look-ahead through iteration 287
Relationship with multiply--add look-ahead 288
Parallelism in annihilation-reording look-ahead 290
Pipelined and block processing implementations 291
Invariance of bounded input and bounded output 294
Pipelined CORDIC-Based RLS Adaptive Filters 294
Pipelined QRD-RLS with implicit weight extraction 295
Stability analysis 297
Pipelined QRD-RLS with explicit weight extraction 299
Conclusion 302
Appendix 305
References 307
11 Weight Extraction of Fast QRD-RLS Algorithms 309
Stefan Werner and Mohammed Mobien 309
FQRD-RLS Preliminaries 310
QR decomposition algorithms 310
FQR_POS_B algorithm 311
System Identification with FQRD-RLS 313
Weight extraction in the FQRD-RLS algorithm 314
Example 316
Burst-trained Equalizer with FQRD-RLS 318
Problem description 319
Equivalent-output filtering 319
Equivalent-output filtering with explicit weightextraction 321
Example 323
Active Noise Control and FQRD-RLS 324
Filtered-x RLS 325
Modified filtered-x FQRD-RLS 326
Example 329
Multichannel and Lattice Implementations 330
Conclusion 330
References 331
12 On Linearly Constrained QRD-Based Algorithms 333
Shiunn-Jang Chern 333
Introduction 333
Optimal Linearly Constrained QRD-LS Filter 335
The Adaptive LC-IQRD-RLS Filtering Algorithm 337
The Adaptive GSC-IQRD-RLS Algorithm 341
Applications 345
Application 1: Adaptive LCMV filtering for spectrum estimation 345
Application 2: Adaptive LCMV antenna array beamformer 348
Conclusion 353
References 353
Index 356