For almost 50 years the Kalman filter has been the accepted approach to tracking filter engineering. At the start of the Satellite Age in 1958, Gauss-Newton tracking filters were tried but had to be ruled out for real-time use because of the speed limitations of existing computers. In their place two new algorithms were devised, first the Swerling filter and then the Kalman filter, both of which could be run in real time on the machines of that era. It was nevertheless observed that Gauss-Newton possessed some superior properties, particularly with regard to stability. Computer speed has now vastly increased and so Gauss-Newton need no longer be ruled out. The almost one hour that it took to execute Gauss-Newton in 1958 is now down to a few tens of milliseconds on readily available machines, and could soon be down to microseconds if computer technology continues to progress as it has done in recent years. It is on this basis that Morrison presents his approach. The book provides a complete theoretical background, and then discusses in detail the Gauss-Newton filters. Of particular interest is a new approach to the tracking of maneuvering targets that is made possible by these filters. The book also covers the expanding and fading memory polynomial filters based on the Legendre and Laguerre orthogonal polynomials, and how these can be used in conjunction with Gauss-Newton. Fourteen carefully constructed computer programs cover the theoretical background, and also demonstrate the power of the Gauss-Newton and polynomial filters. Two of these programs include Kalman, Swerling and Gauss-Newton filters, all three processing identical data. These demonstrate Kalman and Swerling instability to which Gauss-Newton is immune, and also the fact that if an attempt is made to forestall Kalman and Swerling instability by the use of a Q matrix, then they are no longer Cramer-Rao consistent and become noticeably less accurate than the always Cramer-Rao consistent Gauss-Newton filters.
Author(s): Norman Morrison
Series: IET Radar, Sonar and Navigation Series 23
Publisher: The Institution of Engineering and Technology
Year: 2012
Language: English
Pages: xxviii+548
Tracking Filter Engineering: The Gauss–Newton and Polynomial Filters......Page 4
Contents......Page 8
Preface......Page 18
Words containing the letter Z......Page 26
Acknowledgements......Page 27
Why this book?......Page 30
Organisation......Page 31
Part 1: Background......Page 34
1.1 The reader’s educational background......Page 36
1.2 Motivation for writing this book......Page 37
1.4 Scope of the book......Page 39
1.5.2 In a simulator......Page 42
1.5.2.1 Single shot......Page 43
1.5.2.2 Monte-Carlo......Page 44
1.6 Notation......Page 45
1.6.1 Accuracy......Page 49
1.7 Two important words......Page 50
1.8 The filtering procedure......Page 51
1.9 Error/covariance-matrix consistency......Page 55
1.10.1 Univariate Cramér–Rao consistency......Page 56
1.10.2 Multivariate Cramér–Rao consistency......Page 57
1.11 Considering ECM and CR consistency together......Page 59
1.12 Kalman/Swerling instability......Page 61
1.13 Filter memory......Page 65
1.14 The eight performance monitors......Page 66
1.15 What can this book do for you?......Page 67
Closing comments......Page 69
Appendix 1.1: Filter memory......Page 72
Mode 1: fixed memory......Page 73
Mode 2: variable-length memory......Page 74
Mode 3: expanding memory......Page 75
Fading......Page 76
2.1 Linearity......Page 78
2.1.1 Sets of linear equations......Page 79
2.1.3 Linearity and differential equations......Page 80
2.1.4 Constant coefficient linear DEs......Page 81
2.1.5 Time-varying linear DEs......Page 82
2.1.6 Nonlinear DEs......Page 83
2.2 The two types of models......Page 86
2.2.1 The external model......Page 87
2.2.1.1 Fundamental assumption on which this book is based......Page 88
2.2.3 Our approach to DEs......Page 90
2.3.1 Notation......Page 91
2.3.2 The transition matrix and the transition equation......Page 92
2.3.4 The observed trajectory......Page 94
2.3.5 Working in 3-dimensional space......Page 95
2.3.6 Equally spaced observation instants......Page 98
2.4 Models based on constant-coefficient linear DEs......Page 100
2.4.1 One way to derive transition matrices......Page 101
2.4.3 A general way to find transition matrices for constant-coefficient linear DEs......Page 102
2.5 Models based on time-varying linear DEs......Page 104
2.5.2 Obtaining the transition matrix Φ(tn+ζ, tn)......Page 106
2.6 Models based on nonlinear DEs......Page 107
2.6.1 The method of local linearization......Page 109
2.6.2 Using the results from time-varying linear DEs......Page 112
2.6.3 Summary......Page 115
2.6.4 Examples of analytical solutions......Page 116
2.7 Numerical partial differentiation......Page 122
Appendix 2.1: Linear independence of a set of vectors......Page 124
Appendix 2.2: The polynomial transition matrices......Page 125
Appendix 2.3: Derivation of the DE for the transition matrix Φ(tn+ζ,tn)......Page 128
Appendix 2.4: The method of local linearization......Page 130
Appendix 2.5: Proof of Theorem 2.1: Every transition matrix Φ(ζ) is nonsingular......Page 132
Appendix 2.6: A general way to find transition matrices......Page 133
Using equation (A2.6.7) to find transition matrices......Page 134
3.1 How filtering works......Page 138
3.1.2 The observation equations......Page 140
3.1.3 The four cases......Page 141
3.2 Case 1: Linear filter model, linear observation equation......Page 142
3.2.1 Sequences of observation vectors......Page 143
3.3 Case 4: Nonlinear filter model, nonlinear observation equation......Page 146
3.3.1 Local linearization applied to observation equations......Page 149
3.3.2 Sequences of observations......Page 153
3.4 Case 3: Nonlinear filter model, linear observation equation......Page 154
3.5 Case 2: Linear filter model, nonlinear observation equation......Page 158
3.6 Summary......Page 161
3.7 Incorporating a T matrix into the filter......Page 162
3.7.1 Conclusion......Page 165
Appendix 3.1: ENU (east–north–up) coordinates......Page 166
4.1 Random variables......Page 168
4.1.1 Averages and expectations......Page 170
4.1.2 Variance and standard deviation......Page 171
4.1.3 Covariance matrices – actual and supposed......Page 172
4.2.2 Random matrices......Page 173
4.2.3 Covariance matrices......Page 175
4.2.4 Covariance matrices – theoretical and actual......Page 176
4.2.5 The correlation matrix......Page 177
4.2.6 Uncorrelated random vectors......Page 178
4.2.7 Linear transformation of a random vector......Page 179
4.2.9 The covariance matrix of the sum or difference of uncorrelated vectors......Page 181
4.2.10 Correlation and independence......Page 183
4.3.1 The positive-definite property......Page 184
4.3.2 Geometric interpretation......Page 187
4.3.3 Three worked examples......Page 188
4.4 Properties of positive-definite matrices......Page 190
4.4.1 The rank of a matrix......Page 192
4.4.2 Three important theorems regarding positive-definite matrices......Page 193
4.5.1 Positive-semidefinite matrices......Page 195
4.5.2 Properties of positive-semidefinite matrices......Page 196
4.5.3 Important facts from linear algebra......Page 197
Appendix 4.1: Geometric interpretation of the positive-definite property......Page 198
5.1.1 The transformation equations......Page 202
5.1.2 Transforming the covariance matrix in a nonlinear transformation......Page 204
5.1.3 Three final items......Page 207
5.1.4 Summary......Page 209
5.2 The covariance matrix of the observation errors......Page 210
5.3.1 The actual estimation-error vector N*......Page 214
5.3.2 The filter matrix W......Page 215
5.3.3 The filter covariance matrix S*......Page 216
5.3.4 Error/covariance-matrix consistency......Page 217
5.5 The actual estimation-error covariance matrix......Page 218
5.5.1 Comment regarding N*......Page 219
5.6 The column-rank of the T matrices......Page 220
Appendix 5.1: Nonlinear transformation of random vectors and covariance matrices......Page 222
Appendix 5.2: Linear independence of the rows of W......Page 224
6.2 The ensemble......Page 226
6.3 Bias errors in the observations......Page 228
6.3.1 Calibration and bore-sighting......Page 229
6.4.1 The random errors in the estimate......Page 231
6.4.2 The bias errors in the estimate......Page 232
6.5 The exactness constraint......Page 233
6.6 The infinitely many W matrices that satisfy the exactness constraint......Page 235
6.7 When the observation vector is biased......Page 236
6.8 The filter model differs from the external model......Page 237
6.10 Summary......Page 240
Appendix 6.1: Carl Friedrich Gauss on random and bias errors......Page 242
Appendix 6.2: Proof of Theorem 6.2......Page 244
7.1 End-to-end......Page 248
7.2 The matrix-to-matrix ECM test......Page 249
7.2.1 Comparing two matrices......Page 252
7.2.2 A few words of caution regarding ratio matrices......Page 253
7.2.3 An actual example......Page 254
7.3 Block diagram of the three tests......Page 256
7.4 The multivariate-Gaussian and the Chi-squared PDFs......Page 258
7.5.1 The single-shot 3-sigma ECM test......Page 261
7.6 The single-shot Chi-squared ECM test......Page 263
7.6.1 The single-shot Chi-squared ECM test......Page 264
7.7 Failure of the 3-sigma and Chi-squared tests......Page 265
7.8.2 Matrix inversion problems exist......Page 267
7.9 Four illustrative computer runs......Page 269
7.10 Final comments......Page 270
Linear transformations......Page 272
Applications to filter engineering......Page 273
Part 2: Non-recursive filtering......Page 276
8.1.1 Minimum variance......Page 278
8.2 The residuals......Page 279
8.2.1 The sum of the weighted squared residuals......Page 282
8.3 Deriving the MVA: Method 1......Page 284
8.3.1 Finding X*minvar......Page 285
8.3.2 Obtaining Version 2 of the algorithm......Page 286
8.4 Attributes of the MVA......Page 287
8.4.1 The ECM consistency of the MVA......Page 288
8.4.2 Empirical verification......Page 290
8.4.3 The CR consistency of the MVA......Page 291
8.5 The Gauss–Aitken filters – Versions 1 and 2......Page 292
8.5.1.1 Stage 1: wait until sufficient observations have been received......Page 295
8.5.1.2 Stage 2: operating the filters......Page 297
8.6.1 Filter memory......Page 298
8.6.2 The filter model......Page 299
8.8.1 The matrix RY and its inverse......Page 300
8.9 Non-recursive and recursive minimum variance......Page 301
8.9.1 Rule for combining observations......Page 302
8.9.2 Non-recursive and recursive......Page 304
8.9.3 The two forms of the MVA......Page 305
8.9.4 Forming a higher dimension minimum-variance estimate......Page 307
8.9.4.1 Summary......Page 310
8.9.5 Further extensions......Page 311
8.9.6 Data fusion......Page 312
8.9.7 Recursive algorithms must be initialized......Page 313
8.9.9 Fundamental assumption when combining observations......Page 314
Appendix 8.1: Minimization of e(X∗n,n)......Page 316
Appendix 8.2: The MVA filter covariance matrix S∗minvar......Page 318
Appendix 8.3: Obtaining the covariance matrix RY......Page 319
9 Minimum variance and the Gauss–Newton filters......Page 320
9.1.1 Stating the problem in general terms......Page 321
9.1.2 Stating the problem formally......Page 324
9.1.3 Solving the problem......Page 325
9.1.4 What minimum variance means......Page 326
9.1.6 Minimum variance and Cramér–Rao......Page 330
9.1.7 Minimum variance under prediction or retrodiction......Page 331
9.2 The three CR consistency tests......Page 332
9.4 Minimum variance and least squares......Page 335
9.5 The Gauss–Newton filters......Page 336
9.5.1 Cycle and iteration......Page 337
9.5.2 The six Gauss–Newton filters......Page 338
9.7 Enhancements to the Gauss–Newton filters......Page 340
Appendix 9.1: Proof of Theorem 9.1......Page 342
A9.2.1 Minimum variance......Page 345
A9.2.2 Cramér–Rao......Page 346
A9.2.3 Multivariate Gaussian errors......Page 347
Appendix 9.3: Minimum variance and maximum likelihood......Page 349
Appendix 9.4: Excerpt from ‘Theory of the Combination of Observations Least Subject to Errors’......Page 350
10.2.1 Kinds of manoeuvres......Page 352
10.2.4 Number of targets......Page 354
10.2.5 The T matrix......Page 355
10.2.6 The four manoeuvre sequences......Page 356
10.3.1 Overview......Page 357
10.3.2 MCA-1 in detail......Page 358
10.3.3 Two examples of the MCA in action......Page 363
10.3.4 Summary......Page 367
10.4 Testing for goodness-of-fit – a brief description......Page 368
10.4.1 Overview of the GOF test......Page 369
10.4.2 Comments......Page 370
10.5 Stand-alone implementation of the GOF test......Page 371
10.5.1 Demonstrations......Page 372
Appendix 10.1: MCA-2......Page 376
A10.1.1 Operation of MCA-2......Page 377
A10.1.3 Selecting the degree which gives the best fit......Page 378
Appendix 10.2: Theorem 10.1 on which the GOF test is based......Page 383
Part 3: Recursive filtering......Page 386
11.1.1 What exactly is the Kalman filter?......Page 388
11.1.2 The nonrecursive/recursive duality......Page 389
11.2 The Swerling filters......Page 390
11.3.1 Process noise and spontaneous ECM inconsistency......Page 393
11.3.2 Examples of spontaneous Kalman/Swerling ECM inconsistency (instability)......Page 395
11.3.3 Derivation of the Kalman filter equations......Page 396
11.4.1 Comments......Page 398
11.5 The Kalman/Swerling inconsistency dilemma......Page 399
11.6 Conclusion......Page 400
Appendix 11.1: Derivation of the Case-1 Kalman filter......Page 402
Appendix 11.2: The Kalman/Swerling inconsistency-dilemma analytical proof......Page 404
13_Gauss_Newton_C......Page 408
14_Orbit_Track......Page 409
Appendix 11.4: Growth in the CR inconsistency of the extended Kalman and Swerling filters that include Q matrices......Page 412
12.1 Overview......Page 418
12.2.1 The five assumptions......Page 419
12.2.4 Applications......Page 420
12.2.5 Cycle times......Page 422
12.2.8 Block diagram......Page 424
12.2.9 Two ways to obtain Z* and X*......Page 428
12.2.11 Combing......Page 429
12.2.12 The EMP filters are self-initializing......Page 432
12.2.13 The FMP filters are not self-initializing......Page 435
12.2.14 The EMP filters have an expanding memory......Page 436
12.2.15 The FMP filters have a fading memory......Page 437
12.2.16 Variance reduction......Page 440
12.2.17 The VRF expressions for the 1-step predictor EMP filters......Page 443
12.2.18 The VRF expressions for the 1-step predictor FMP filters......Page 447
12.2.19 Approximate expressions for the denormalized covariance matrices......Page 450
12.2.20 Tracking ability, ECM consistency and CR consistency......Page 453
12.2.21 Choice of coordinate system......Page 454
12.2.22 Outlier exclusion......Page 458
12.2.24 Quantifying the memory lengths of the FMP filters......Page 459
12.2.25 Quick settling......Page 462
12.2.26 Fixed-length and variable-length EMP filtering......Page 467
12.2.27 The composite EMP/FMP filter......Page 470
12.2.28 Prefiltering......Page 480
12.2.29 The sigma monitoring test......Page 486
Appendix 12.1: One-step predictor EMP algorithms, degrees 0 to 4......Page 490
Appendix 12.2: One-step predictor FMP algorithms, degrees 0 to 4......Page 492
Appendix 12.3: Current estimate EMP algorithms, degrees 0 to 4......Page 494
Appendix 12.4: Current estimate FMP algorithms, degrees 0 to 4......Page 496
13.1.1 The approximating polynomial......Page 498
13.1.2 Classical least squares......Page 500
13.1.3 The discrete Legendre orthogonal polynomials......Page 501
13.1.5 Least squares using the Legendre polynomials......Page 504
13.1.6 Using the β’s to write the approximating polynomial......Page 506
13.1.7 Estimating the true state vector......Page 507
13.1.8.1 The general expression for the EMP weights for any degree m......Page 509
13.2 The EMP covariance matrices......Page 510
13.2.1 Algebraic expressions for the diagonal elements......Page 512
13.2.2 Computing numerical values for the covariance matrices......Page 518
13.2.3 Recursion formulas for the variances of the 0th-derivative estimates......Page 521
13.3 Deriving the FMP equations......Page 522
13.3.1 The approximating polynomials......Page 523
13.3.2 Classical least squares......Page 525
13.3.3 The discrete Laguerre orthogonal polynomials......Page 526
13.3.5 Least squares using the Laguerre polynomials......Page 529
13.3.7 Estimating the true state vector......Page 531
13.3.8 The FMP recursive formulation......Page 533
13.4.1 The normalized FMP covariance matrices......Page 534
13.4.2 Denormalization......Page 535
13.4.3 Validation of the expressions for the FMP covariance matrices......Page 537
Appendix 13.1: The discrete Legendre orthogonal polynomials......Page 538
Appendix 13.2: The three Legendre P matrices......Page 539
Appendix 13.3: The discrete Laguerre orthogonal polynomials......Page 542
Appendix 13.4: The Laguerre A(θ) matrix......Page 543
Appendix 13.5: The Laguerre F(s,θ) matrix......Page 544
References......Page 546
Index......Page 558
