Kalman Filter Is All You Need: Optimization Works When Noise Estimation Fails
Authors: Ido Greenberg
Shie Mannor
Netanel Yannay
Venue: ICLR 2022 Submitted (2022)
Keywords: Kalman Filter
noise estimation
optimization
gradient descent
parameterization

Abstract: Determining the noise parameters of a Kalman Filter (KF) has been studied for decades. A huge body of research focuses on the task of noise estimation under various conditions, since precise noise estimation is considered equivalent to minimization of the filtering errors. However, we show that even a small violation of the KF assumptions can significantly modify the effective noise, breaking the equivalence between the tasks and making noise estimation an inferior strategy. We show that such violations are common, and are often not trivial to handle or even notice. Consequentially, we argue that a robust solution is needed - rather than choosing a dedicated model per problem.
To that end, we apply gradient-based optimization to the filtering errors directly, with relation to an efficient parameterization of the symmetric and positive-definite parameters of the KF. In a variety of state-estimation and tracking problems, we show that the optimization improves both the accuracy of the KF and its robustness to design decisions.
In addition, we demonstrate how an optimized neural network model can seem to reduce the errors significantly compared to a KF - and how this reduction vanishes once the KF is optimized similarly. This indicates how complicated models can be wrongly identified as superior to the KF, while in fact they were merely more optimized.

Under review as a conference paper at ICLR 2022
KALMAN FILTER Is ALL YOU NEED: OPTIMIZATION WORKS WHEN NOISE ESTIMATION FAILS
Anonymous authors Paper under double-blind review
ABSTRACT
Determining the noise parameters of a Kalman Filter (KF) has been studied for decades. huge body of research focuses on the task of noise estimation under various conditions, since precise noise estimation is considered equivalent minimization of the filtering errors. However, we show that even a small violation of the KF assumptions can significantly modify the effective noise, breaking the equivalence between the tasks and making noise estimation an inferior strategy. We show that such violations common, and are often not trivial handle even notice. Consequentially, we argue that robust solution is needed rather than choosing dedicated model per problem. To that end, we apply gradient- based optimization to the filtering errors directly, with relation to an efficient parameterization of the symmetric and positive-definite parameters of the KF. In a variety of state-estimation and tracking problems, show that the optimization improves both the accuracy the KF and its robustness to design decisions. addition, demonstrate how optimized neural network model can seem reduce the errors significantly compared to a KF and how this reduction vanishes once the KF is optimized similarly. This indicates how complicated models be wrongly identified as superior to the KP, while in fact they were merely more optimized.
INTRODUCTION
The Kalman Filter (KF) Kalman 1960)
a celebrated method for linear filtering and prediction, with applications in many fields incl including tracking. guidance, navigation and control (Zarchan and Musoff 2000 Kirubarajan 2002). Due to its simplicity and robustness, it remains highly popular with over 10,000 citations in the last 5 years alone (Google Scholar 202T) despite the rise of many non-linear sequential prediction models (e.g., recurrent neural networks). following model for dynamic system:
The KF relies on the
X = F,X, + Wt
(wr ~ ((, (vr ~ NO, R))
(I)
2, H,,X,
where Xg the state of the system at time (whose estimation is usually the goal), and its dynamics are modeled by the linear operator F; up to the random noise wa with covariance Q; and Z, is the observation, which modeled by the linear operator H, up to the noise vi with covariance R. When the operators F,, H, are not assumed to depend on time, the notation may be simplified to F, H.
To use the KF, one must determine the noise parameters Q, R. The filtering errors (i.e., estimation errors of the states (X+}) are minimized when Q and R correspond to the true covariance matrices of the noise (Humpherys et al., 2012). Thus, these parameters are usually determined by noise estimation. In absence of system state data {5,} (the "ground truth"). many methods have been suggested to determine Q and R from observations data { alone (Abbeel et al. 2005 Odelson al. 2006 Zanni et al. 2017 Park et al. 2019). When ground-truth data is available. however, noise estimation trivially reduces to calculation of the sample covariance matrices (Lacey 1998):
R := Coo((, H,r:)+),
Q Cov (fx+11 - F.).).).
Indeed, as stated by Odelson et al. (2006), "the more systematic and preferable approach to determine the filter gain is to estimate the covariances from data". Our work focuses such problems with ground-trun truth available for learning (but not for inference after the learning, of course), which was motivated by real-world Doppler radar estimation problem.

---

Under review as a conference paper at ICLR 2022
Noise estimation is often not optimal: The equivalence between noise estimation and errors minimization can be proved under the standard KF assumptions - that is, known and linear dynamics and observation models (Fe, H₂), with i.d and Hermally-distribun le al. 2012). However, as put by Thomson (1994), "experience with real-world data soon convinces one that stationarity and Gaussianity are fairy tales invented for the amusement of undergraduates" and linearity and independence can be safely added to this list. Therefore, under realistic assumptions, the covariance of the noise does not necessarily correspond to optimal filtering.
noises (fw,), {vr }) (Humpherys
We introduce a case study in the context of radar tracking, where we demonstrate that even using the true covariance of the noise ("oracle" noise-estimation) sub-optimal in variety of scenarios in- cluding very simple scenarios with relatively minor violation of the KF assumptions. In Appendices E and we also analyze this phenomenon analytically for two private cases mon-linearity in Doppler radar and non-i.i.d noise in lidar), where the violation of a single KF assumption is shown to modify the effective noise. By providing this extensive evidence that noise-estimation is sub-optimal way to tune a KF even in presence of -ystess-tates ground-truth data, we re-open a problem that was considered solved for decades [Kalman] 1960).
We also show that seemingly small changes in the properties of the scenario may lead to major changes in the desired design of the KF, e.g., whether to use a KF or an Extended KF (Sorenson, 1985). In certain cases, the design choices are not trivial to make even if noticed. As a result, it is impractical to manually choose or develop a variant of the KF for every problem. Rather, we should assume that our model is sub-optimal, and leverage data to deal with the sub-optimality as robustly as possible.
easy to overlook (c.g., Cartesian vs. spherical coordinates), and
Optimization is optimal: We consider Q and as model parameters that should be optimized with respect to the filtering errors (i.e., system-state estimation errors) rather than estimating the noise. While both noise estimation and errors optimization rely on exploitation of data, only the latter explicitly addresses the actual goal of solving the filtering problem.
Gradient-based optimization methods are usually effective in the field of machine learning. but applying them naively to the entries of Q and R may violate the symmetry and positive-definice (SPD) constraints of the covariance matrices. Indeed, even works that come as far as optimizing Q and R (instead of estimating the noise) usually apply limited optimization methods, e.g., grid- search (Coskun et al.) 2017) or diagonal restriction of the covariance matrices (Formentin and Bittanti 2014 Li et al. 2019). To address this issue, we use a parameterization based on Cholesky decomposition (Horn and Johnson 1985). which allows us to apply gradient-based optimization to SPD matrices. This method computationally efficient compared to other general gradient-baas based methods for SPD optimization (Tsuda et al. [2055] Tibshirani 2015).
We demonstrate that the optimization reduces the errors of the KF consistently: over different variants of the KF, over different violations of KF assumptions, over different domains (tracking from radar, video or lidar), over small and large training datasets, and even under distributional shifts between train and test datasets. Furthermore, we show that optimization improves the robustness to design decisions, by shrinking the performance gaps between different variants of the KF.
As explained above, we extensively justify the need to optimize the KF in many practical problems, and suggest a simple solution which is effective, robust, computationally efficient, and relies on standard tools in supervised machine learning. As result, we believe that in the scope of filtering problems with available ground-trute whenever the KF assumptions are not guaitty-guaratteedd the suggested optimization method should become the new standard procedure for the KF tuning.
Unfair comparison: Many learning algorithms have been suggested to address non- non-lineann con-aiicay in filtering problems, e.g., based on Recurrent Neural Networks (RNN). Such works often use linear tool such as the KF as a baseline for comparison with tuning parameters being sometimes ignored (Gao et al. 2019), sometimes based on noise estimation (fa Dai et al. 2020), and sometimes optimized in limited manner using trial-and-error (Jamil et al.) 2020) or grid-search (Coskun et al. (017). Our findings imply that such a methodology yields optr-optimistic conclusions, since the baseline is not optimized to the same level as the learning model. This may result in adoption of over- complicated algorithms with no actual added value. Instead, any learning algorithm should be compared to a baseline that is optimized using similar method (e.g., gradient-descent with respect the errors).
2

---

Under review as a conference paper at ICLR 2022
Indeed, we consider an extension of the KF based on LSTM, which is the key component in many SOTA algorithms for non- mineir sequential prediction in recent years (Neu et al. 2021). For radar tracking with non-linear motion, we demonstrate how the LSTM seems to provide a significant improvement over the KF. Then, we show that the whole improvement comes from optimization of parameters, and not from the expressive non-linear architecture. In particular, this result demonstrates the competitiveness of our suggested method versus SOTA sequential prediction models.
Recent works in the area of machine learning have already shown that advanced algorithms often obtain most of their improvement from implementation nuances (Engstrom et al. 2019) Andrychowicz al. 2020) Henderson et al. 2017). Our work continues this line of thinking and raises awareness to this issue in the domain of filtering problems.
Contribution: We show (empirically and analytically) that the gold-standane noise estimation method to tune the KF given ground-truth data is often sub-optimal; demonstrate how this leads to underevaluation of the KF compared to optimized filtering models such as neural networks; suggest a simple method to optimize the KF, using gradient-based optimization with Cholesky parameterization; and extensively demonstrate its improved accuracy and its robustness to model misspecification.
This work relies on the availability of ground-truth system-states in the training data to allow supervised learning. Ground-truth data often available from simulations, controlled experiments or manual labeling. Within this scope, show that although noise estimation is straight- forward (Equation 2) it is often not the right task to address. Another limitation is in the theoretical guarantees of gradient-based optimization (see Appendix D. despite its wide success in many fields.
Limitations:
The paper is organized as follows: Section reviews the KF. Section 3 introduces our method for efficient KF optimization. Section justiffes the necessity of KF optimization through detailed case study. ( neural version of the KF which reduces the errors compared to a standard KF but not when compared to an optimized KF, Section discusses related works.
PRELIMINARIES: THE KALMAN FILTER ALGORITHM
The KF algorithm (almann 1960
Prodict
X p.
= Prxe
Humpherys et al., 2012) relies on Equa- tion for dynamic system model. keeps an estimate of the state X,, represented the mean 2, and covariance P. of a normal distribution. As shown Figure [ it alternately predicts the next state using the dynamics model (prediction step), and processes new information from incoming observations (update or filtering step).
P.Pefi +Q
Xt+1, Pt1
t t+1
Xx,
Update
K (H,P + R)-1 x, = x +K(,, 1 Hxxf)
Zt
Pt = (1 KHOPP
The KF yields optimal state estimations but only under a restrictive set of assump- tions (Kalman, 1960), as specified in Def- inition 2.1 Note that normality of the noise excluded since it is not necessary for optimal- ity (Humpherys et al. 2012), although it is also often assumed.
Figure 1: The KF algorithm. The prediction step is based on the motion model Ft with noise whereas the update step hased the observation model He with noise R.
Definition 2.1 (KF assumptions). F,, H, of Equation D are known matrices that do not depend on the state (i.c.. correspond to linear models); Wi, 1/; i.i.d random variables with zero-mean and constant, known covariance matrices Q, Rt respectively; and the initial state distribution known.
Certain assumptions violating in Definition 2.1 can be partially handled by variations of the KF, such as the Extended KF (EKF) (Sorenson 1985 which replaces the linear models F;, H,, with local linear approximations, and the Unscented KF (UKF) (Wan and Van Der Merwe, 2000 which applies the filtering through sigma-point sampled from the estimated distribution. The use of multiple tracking models alternately is also possible using switching mechanisms (Mazor al. 1998).
While F2 and H, are usually determined based on domain knowledge, Q and R are often estimated from data the covariance of the noise. As mentioned in Section T this can be done using Equation
3

---

Under review as a conference paper at ICLR 2022
if ground-truth data is available, or using more sophisticated methods otherwise Odelson et al. 2006
Feng et al. 2014 Park et al. 2019).
See Appendix A for detailed introduction of the KF and recurrent neural networks (RNN, LSTM).
KF OPTIMIZATION USING CHOLESKY PARAMETERIZZATION
The performance of a KF strongly depends on its parameters Q and R (Formentin and Bittanti] 2014).
These parameters are usually regarded estimators of the noise covariance motion and observation, respectively (Lacey) 1998), and are estimated accordingly. Although optimization has been suggested for the KF in the past (Abbeel al., 2005), it was often viewed as a fallback solution (Odelson et al.) 2006), for cases where direct estimation is not possible (e.g., the true states are unavailable in the data (Feng et al. 2014)). Accordingly, we define our baseline method for this work:
Method 1 (Estimated KF). KF whose parameters Q, R were determined from data using Equation
The preference of noise estimation relies on the fact that the KF with parameters corresponding to the noise covariances- minimizes the square filtering errors (MSE) of the estimates of the system-states {X₂). This holds under Assumptions 2.1 (Humpherys et al. 2012). Hence, equivalently, we could explicitly look for the parameters that minimize the MSE, e.g., using the Adam algorithm (Diederik P. Kingma 2014). Adam is popular variant of the well-known gradient-descent algorithm, and has achieved remarkable results in many optimization problems in the field of machine learning in recent years, including in non-convex problems where local-minima exist (Zhong al. 2020).
Numeric optimization is more complicated than computing two covariance matrices, but is shown to be beneficial in Sections 4 and Stable optimization algorithms available in several open- source packages, e.g., Py P (Paszke et al., 2019), which supports gradient- proppagaionn through matrix-inversion (as needed for the KF computation)). As demonstrated in Sections 4 the Py PyTorch implementation of Adam provides stable results on MSE- OSS--optiizatiinn of KF. This is conceivable, as the KF is arguably a simple model in terms of mathematical sophistication and number of parameters.
One major challenge in the KF parameters optimization is that both Q and R correspond to covariance matrices, which are symmetric and positive definite (SPD): a naive numeric optimization of their entries may ruin the SPD structure. This difficulty often motivates optimization methods that avoid gradients (Abbeel et al. 2005), or even the restriction of Q and R to be diagonal (Li et al.) 2019). Indeed, Formentin and Bittanti (2014) pointed out that "since both the covariance matrices must be constrained to be positive defintef Q and It are often parameterized as diagonal matrices".
To allow Adam to optimize the non-diagonal Q and It we use the Cholesky parameterization (Pinheiro) and Bates, 1996). It relies on Cholesky decomposition (Horn and Johnson 1985). which states that any SPD matrix A gnxa can be written A LL where L is lower-triangllar with positive entries along its diagonal. The reversed claim is also true: for any lower-triangular L with positive diagonal, LLL is SPD. Now consider the parameterization of A using the following and n parameters to flog Lu Li Clearly, the transformation from the parameters to the SPD matrix A = LLT is differentiable and outputs a SPD matrix for any realization of the parameters in Ro(n+1//2 Thus, apply Adam (or any other gradient-base -aaed method) to optimize these parameters without worrying about the SPD constraints. This approach, which is presented in more general framework in Appendix C and is implemented our code is used in our KF optimization method as follows:
(2) +n mm++l) parameters: (2) parameters correspond to {Lig)
Method 2 (Optimized KF). A KF whose parameters Q, R were determined from data by optimizing the . E of the state-estimates, using Adam algorithm with relation to a Cholesky parameterization of Q and R, as described in detail in Appendix B.T
Note that other methods exist for SPD optimization, but require SVD-decomposition every iteration and thus are computationally heavier, e.g.. vaarix-exxponet (suuda et al.) 2005) and projected gradient-descent with respect to the SPD cone (Tibshirani 2015). The Cholesky parameterization only requires a single matrix multiplication, and thus is both efficient and easy to implement. To the best of our knowledge, this parameterization is not used at all for supervised optimization of KF.
4

---

Under review as a conference paper at ICLR 2022
4 KALMAN FILTER CONFIGURATION AND OPTIMIZATION: A CASE STUDY
In this section, we introduce a detailed case study to compare noise estimation and errors optimization in the KF. As mentioned in Section 2 the two are equivalent only under Assumptions 2.1 (Humpherys) et al., 2012). Some of these assumptions are clearly violated in realistic scenarios, while other violations may be less obvious. For example, even if a radar's noise i.i.d in spherical coordinates, is not so in Cartesian coordinates (see Appendix A.5).
The need to rely on many assumptions might explain why there are several extensions and design decisions in a KF configuration. This includes the choice between KF and EKF; the choice between educated state initialization and a simple uniform prior (Linderoth et al. 2011); and certain choices that may be made without noticing, such the coordinates of the state representation.
The case study below justifies the following claims:
Design decisions in a are often nontrivial to make and are potentially significant.
2. Tuning KF by noise estimation is often highly sub-optimal even in very simple scenarios.
3. Tuning a KF by optimization improves both accuracy and robustness to design decisions.
4. KF optimization using Method is robust to distributional shifts (Appendix G and small training datasets (Appendix H
These claims imply that the popular KF algorithm may not be exploited to its full potential. Further- more, many works that compare learning algorithms to KF baseline conduct an "unfair" comparison, as the learning algorithms are optimized and the KF is not. This may lead to adoption of unnecessarily
complicated algorithms, as demonstrated in Section 5 Indeed, in many works the tuning of the baseline KF is either ignored in the report (Gao et al. 2019) relies estimation (or knowledge) of
the noise (fa Dai et al. 2020: D Jamil et al. 2020 as demonstrated extensively in Section 6
4.1 SETUP AND METHODOLOGY
In the case study of radar tracking, each target is represented by a sequence of (unknown) states in consecutive time-steps, and a corresponding sequence of radar measurements. A state full = (Tar Ty. F2, Tezz Tey: Tuz) E RR6 consists of 3D location and velocity. We also denote x == (I2, )²)] T E IR3 for the location alone (or Ttarget, E R33 for the location of a certain target at time t). An observation 2 E R4 consists noisy measurements of range, azimuth, elevation and Doppler signal. Note that the former three correspond to noisy measurement of x in spherical coordinates, and the latter one measures the projection of velocity onto the radial direction x. The goal minimize the error of the point-estimate of the state: MSF. Etageet E, (Frarget,t Fiarget,
The study considers 5 types of tracking scenarios (benchmarks) and 4 variants of the KF (baselines). For each benchmark and each baseline, we use the benchmark training data to produce one estimated KF (Method IT and one optimized KF (OKF, Method 2). We then evaluate the errors of both models on the test data of the benchmark (generated using different seeds than the training data). All experiments were run on eight 19-10900X CPU cores on a single Ubuntu machine.
Figures 2b 2c display a sample of trajectories in the simplest benchmark (Toy), which satisfies all KF assumptions except for linear observation model Hi; and in the complex Free Motion bench- mark, which violates several assumptions. The other benchmarks are demonstrated in Appendix M Figure 2a defines each of the benchmarks more formally as certain subset of the following properties:
anisotropic: horizontal motion is more likely than vertical motion (otherwise motion direc- tion is distributed uniformly).
polar: radar noise is generated i.i.d in spherical coordinates (otherwise noise is Cartesian i..dd which violates the physics of the system).
uncentered: targets not forced to concentrate close to the radar.
acceleration: speed change is allowed (through intervals of constant acceleration).
turns: non-straight motion is allowed.
5

---

Under review as a conference paper at ICLR 2022
anisotropic
uncentered
acceleration
Toy
Free
polar
turrs
1550
3000
300
550
Toy
639
Const_v
130
Const_a 3
free
-2000 1000
(8)
(b)
(c)
Figure 2: (a) Benchmarks (rows) and the properties that define them (columns). Green that the benchmark satisfies the property. (b,c) Targets Toy and Free Motion benchmarks (projected onto XY plane).
The baselines differ from each other by using either KF or EKF, with either Cartesian or spher- ical coordinates for representation of R (the rest of the system is always represented in Cartesian coordinates). As mentioned above, each baseline is tuned once by Method and once by Method] 2 Note that the non-linear observation model requires minor adjustments of the KF baselines and the tuning methods, as explained Appendix AA.3] For the Toy benchmark, the optimal parameters also derived analytically in Appendix E Appendix TepeendixGddemeee demonstrates the robustness of OKF to distributional shifts by training on one benchmark and testing on another. Appendix H repeats the tests for different sizes of training datasets.
We also repeat the experiment for the problem of tracking from video, using MOT20 dataset (Den- dorfer et al. (202)) of real-world pedestrians, with train and test datasets taken from separated videos. For this problem we only consider a KF with Cartesian coordinates, since there is no polar component in the problem. See Appendix for the detailed setup of the video tracking experiments. In addition, we test the OKF in the problem of self-driving state-estimation from lidar measurements (Ap- pendix D. These two domains extend the scope of the experimented KF assumptions violations, since they correspond to linear observation models (unlike the radar benchmarks), with both noisy (lidar) and noiseless (MOT20) observations. For simplified lidar problem, we also derive the optimal parameters analytically in Appendix
4.2 RESULTS
Design decisions not trivial: Table summarizes the tracking errors. The left column in each cell corresponds to Method (standard KF), and shows that in each benchmark, the errors strongly depend on the design decisions (R's coordinates and whether example, EKF is the best design, since the observation model H is non-linear.
EKF). In the Toy benchmark, for
In other benchmarks, however, the winning designs of the non-optimized KF arguably surprising:
1. Under non-isotropic motion direction (all benchmarks except Toy), EKF worse than KF despite the non-linear motion. It is possible that since the horizontal prior reduces the stochasticity of H, the advantage EKF no longer justifies the instability of the derivative- based approximation.
Table 1: Summary of the errors of the various models the various benchmarks (on out-of-sample data). Corresponding confidence intervals are available Figure [4alin appendix. the model names, "O" denotes optimized, "E" denotes extended, and "p" denotes polar, For example, OEKFp is an extended KF with polar (spherical) representation of R and optimized parameters. For KFp, we also consider an oraclo-rcalization of R according the true noise of the simulated radar in spherical coordinates (available only in spherical benchmarks). Note that (1) for any benchmark and any baseline, optimization yields lower than estimation; oracle variant, where noise "estimation" perfect.
(2) remains true even
Benchmark
KF
OKF
KFp
KFp (oracle)
OKFp
EKF
OEKF
EKFp
OEKFp
Toy
151.7
84.2
269.6
116.4
92.8
79.4
123.0
109.1
Close
25.0
24.8
22.6
22.5
22.5
26.4
26.1
24.5
24.1
Const
90.2
90.0
102.3
102.3
89.2
102.5
99.7
112.7
102.1
Const_a
107.5
101.6
118.4
118.3
100.3
110.0
107.0
126.0
108.7
Free
125.9
118.8
145.6
139.3
117.9
135.8
121.9
149.3
120.0

---

Under review as a conference paper at ICLR 2022
2. Even when the observation noise is spherical ii.d, spherical representation of R. is not beneficial unless the targets are forced to concentrate close to the radar (last 3 benchmarks in Table D. It is possible that when the targets are distant, Cartesian coordinates have more important role in expressing the horizontal prior of the motion.
Since the best variant of the KF for each benchmark seems difficult to predict in advance, a practical system cannot rely on choosing the KF variant optimally, and rather has to be robust to this choice.
Prediction-errors distribution on MOT20 (Normalized z-value (KF-OKF): 125)
Optimization is more accurate and robust: Table !
2.00
shows that for every benchmark and every baseline in the radar tracking problem (20 experiments in total), optimization yielded smaller errors than noise estimation (over an out-of-sample test dataset). Note that OKF wins even in the Toy scenario, under the slightest violation of KF assumptions. In addition, the variance between the baselines reduces under optimization, i.c., the opti- mization makes the KF more robust to design decisions (which is also evident in Figure 14a in Appendix [M).
175
KF (dashed=mean)
1550
OKF (dashed=mean)
1.00
0.50
025
0.00
100
quantile
We also studied the performance of KF with a perfect knowledge of the noise covariance matrix R. Note that in the constant-speed benchmarks, the estimation of Q O is already very accurate, hence in these benchmarks the oraele-KF has practically perfect knowledge of both noise covariances. Nonetheless, Table shows that the oracle yields very similar results to KF with estimated parameters. This indicates that the limitation of noise estimation in the KF indeed comes from choosing the wrong goal, and not from estimation inaccuracy.
Figure 3: Prediction errors of KF and OKF on 1208 targets of the test data of MOT20 videos dataset. The MSF of OKF is smaller by 18% with statistical significance of p-value 10 over the test samples.
[Ryy
[Toy) OKF /R
Doo
Figure 3 shows that OKF provides significantly better predictions also in video tracking, where the MSE is reduced by 18% (see Appendix for more details). In addition, in lidar-based state estimation, Appendix [ shows a similar error reduction of 15% and Lemma F:3 exxlains the MS E-Eaaaaaataaee of OKF analytically.
20048
50
14
-
3090
3231
13
2513
10092
0002
3905
14
96
9019
48
3087
3
D60
(a) Estimated
(b) Optimized R
OKF is further demonstrated to be robust to major distributional shifts in Appendix G and to small training datasets in Appendix
Figure 4: The covariance matrix It of the observation noise obtained in a (Cartesian) KF by noise estimation and by optimization, based the dataset of the Toy benchmark. The axes correspond to the observation vari- ables associated with the matrix entries. Note that the noise estimation is quite accurate, as the true variance of the noise is 100 for the positional dimensions and 5" for Doppler. The optimization increases the vari- ance associated with the Doppler signal, as predicted by Lemma The decrease in the other diagonal compo- nents is discussed in Appendix [B
Diagnosis of the KF sub-optimality in Toy scenario: The source of the gap between es- timated and optimized noise parameters can be studied through the simplest Toy benchmark, where the only violation of KF assumptions is the non-lineat observation model H. Since the non-constant entries of H correspond to the Doppler observation, the non-linearity inserts uncertainty to the Doppler observation (in addition to the inherent observation noise). This increases Doppler's effective noise in comparison to the location observation, as shown analytically by Lemma E. in the appendix. This explanation is consistent with Figure 4 the noise associated with Doppler is indeed increased by the optimization. Note that the non-linearity modifies the effective noise in a delicate way, which would not be compensated by naive trial and error of noise inflation deflation.
5 NEURAL KALMAN FILTER: IS NON-LINEAR PREDICTION HELPFUL?
standard Kalman Filter for a tracking task assumes linear motion, as discussed in Section 2 In this section we introduce the Neural Kalman Filter tracking model (NKF), which uses LSTM networks to model non-linear motion, while keeping the framework of the KF namely, the probabilistic representation of the target's state, and the separation between prediction and update steps.
7

---

Under review as a conference paper at ICLR 2022
Every prediction step, NKF uses neural network model to predict the target's 's acceleration 0, and the motion uncer- tainty Qt- Every update step, another network predicts the observation uncertainty Rç- The predicted quantities are incorporated into the standard update equations of the KF, as shown in detail in Figure ii Appendix B For example, the prediction step of NKF is:
AMSE (wrt KF baseline)
12.9K H
-500
12 1444 H
12.9K H
-1000
-1500
12.1K
-2000
-2500
OKF
-3000
NKF
3374
13
wft1 Fxz + (A5),
P + Q
-3500
12<acc<24 24<acc<48 48 <acc<996
where F = F(At) is the constant-velocity motion opera- tor, and a, Q. are predicted by the LSTM (whose input in- cludes the recent observation and the current estimated tar- get's state). Other predictive features were also attempted but failed to provide significant value, as described in Appendix B Note that the neural network predicts the acceleration rather than directly predicting the location. This is intended to regularize the predictive model and to exploit the domain knowledge of kinematics.
scenario
(a)
100
stat
Canget
dbnervartn
3000
KF Ned
OKF
2003
After training NKF over a dataset of simulated targets with random turns and accelerations (see Appendix B. for more details), we tested it on a test dataset. The test dataset similar the training dataset, with different seeds and an extended range of permitted accelerations. As shown Figure 5 NKF significantly reduces the tracking errors compared to a standard KF.
3392
(b)
At this point, seems that the non- con-linear architecture of NKF provides better accuracy in the non-linear problem of radar tracking. However, Figure shows that by shifting the baseline from naive KF to an optimized one, com- pletely eliminate the advantage of NKF, and in fact reduce the eπrors even further. In other words, in this experiment the benefits of NKF come only from optimization and not at all from the expressive architecture. By overlooking the sub-optimality of noise estimation in the KF, we would wrongly adopt the over-complicated NKF.
(a) Relative tracking errors (lower is better) with relation to a standard KF, over targets with different ranges of acceleration. The error-hars represent confidence intervals 95%. The label of each bar represents the corresponding absolute MSE (x x10)). In the training data, the acceleration was limited to 24-48, hence the other ranges measure gen- cralization. While the Neural KF (NKF) significantly better than the standard KF, its advantage is entirely eliminated once we op- timize the KF (OKF). (b) A sample target and the corresponding models outputs (pro- jected onto XY plane). The standard KF has a difficulty to handle some of the turns.
Figure 5:
Note that the optimized KF (OKF) also generalizes well targets with different accelerations than observed in the training, which indicates a certain robustness to distribu- tional shifts. Appendix K extends the experiment to additional variants of NKF, to another tracking benchmark, and to the evaluation metric of likelihood (NLL) in addition to estimation error (MSE). Note that high likelihood score is important for the matching task in a multi-target tracking problem.
Of course, our results do not imply that neural-networks in general cannot be superior to a KF: only that when comparing the two, if the KF not optimized similarly to the neural model, the experimental results may be very misleading. As discussed in Section 6 this wrong methodology is not uncommon in the literature.
RELATED WORK
Noise estimation: When tuning a KF, the system-states are often unavailable in the data (Formentin and Bittanti 2014). Thus, estimation the KF noise parameters from observations alone has been studied for decades, addressed using various methods based on autocorrelation (Mehra) 1970; Carew
and Be langer 1,73), EM (Shumway and Stoffer 2005) and others (Odelson et al. 2006 Feng et al. 2014; Park al. 2019). However, if the states are available, noise estimation reduces Equation and 18 considered a solved problem (Odelson et al., 2006). In this case, we show that although noise estimation is easy, it is often not the right task address.
8

---

Under review as a conference paper at ICLR 2022
Many works addressed the problem of non-stationary noise estimation (Zanni et al. 2017 Akhlaghi ct al. 2017). However, as demonstrated in Sections in certain cases stationary methods are highly competitive if tuned correctly- even in problems with complicated dynamics.
Optimization: In this work we apply gradient-based optimization to the KF with respect to its
errors. Optimization without gradients was already suggested in Abbeel et al. (2005). In practice, "optimization" of the KF is often handled manually using tril-and-erros (Jamil et al. (2200) or
grid-search over possible values of Q and R (Formentin and Bittanti 2014 Coskun et al. 2017) In
other cases, Q and R are restricted to be diagonal (Li et al. [ and Bittanti
2014
Gradient-based optimization of SPD matrices in general was suggested in [suda et al. (2005) using matrix-exponente and is also possible using projected gradient-descent (Tibshirani, 2015)
both rely on SVD-decomposition parameterization that was suggested in Pinheiro and Bates (1996), which requires mere matrix multiplication, and thus is both efficient and easy to implement.
this work, we apply gradient-based optimization using the
In absence of trajectories dataset, recent line of works (Tiamis and Pappas 2020 Goel and Hassibi 2021) applics online optimization within the current trajectory to minimize a regret metric.
Neural Networks (NNs) in filtering problems: Section 5 presents RNN-based extension of the KF, and demonstrates how its advantage over the linear KF vanishes once the KF is optimized. The use of NNs for non- non-linear filtering problems very common in the literature, e.g., in online tracking
prediction (Gao et al. 2019 Dan Iter 2016 Coskun et al., 2017 fa Dai et al. 2020 Ullah et al.
2019), near-online prediction Kim et al. 2018), and offline prediction (Liu et al. 2019b). addition,
while Bewley et al. (016)) apply KF for video tracking from mere object detections, Wojke et al.
(2017) add to the same system a NN that generates visual features as well. NNs were also considered for related problems such as data association (Liu et al. 2019a), model-switching (Deng et al. 2020).
and sensors fusion (Sengupta et al. 2019).
In many works that consider NNs for filtering problems, a KF is used baseline for comparison. However, while the NN parameters are typically optimized with respect to the filtering errors, the
KF parameters tuning is sometimes ignored (Gao et al. 2019 Bai et al., 2020; Zheng al. (2019). sometimes based on estimation (or knowledge) of the noise (fa Dai et al., 2020; Aydogmus and Aydogmus 2015 Revach al. 202T), and sometimes optimized in limited manner mentioned above (Jamil et al. [2200] Coskun et al., 2017: Ullah et al., 2019). Our findings imply that this methodology wrong, since the baseline not optimized the same level the learning model.
Hussein (2014) explicitly discusses the sensitivity of EKF performance to the noise model accuracy. and suggests the solution of NN with supervised learning without considering the same supervised
learning for the EKF.
7 SUMMARY
Through a detailed case study, we demonstrated both analytically and empirically the fragility of the KF assumptions, and how the slightest violation of them may change the effective noise in the problem leading to significant and non-trivial changes in the optimal noise parameters. We addressed this problem using optimization tools from supervised machine learning, and suggested how to apply them efficiently to the SPD parameters of the KF.
We demonstrated the accuracy of our method over different violations of KF assumptions, different domains (radar tracking, vidco tracking and lidar-based state estimation), with relation to different variants of the KF, over small and large training datasets, and even under distributional shifts between train and test datasets. Indeed, once we acknowledged the need for optimization and applied the Cholesky parameterization, the optimization itself performed robustly over all these scenarios. In light of this evidence, we recommend to use our method the default procedure for the KF tuning in presence of ground-truth data, whenever the KF assumptions are not triicly-guaranteed
We also demonstrated one of the consequences of using sub-optimal KF: the common methodology of comparing learning filtering algorithms to classic variants of the KF is misleading, as essentially compares an optimized model non-optimized one. We argued that the baseline method should be optimized similarly to the researched one, e.g., using optimization rather than noise estimation.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY
All the experiments in this work are reproducible using our code including data generation, mod- els training and results analysis. The complete proofs for the theoretical results are available in Appendices and
REFERENCES
Pieter Abbeel, Adam Coates, Michael Montemerlo, Andrew Ng, and Sebastian Thrun. Discriminative training of kalman filters. Robotics: Science and systems, pages 289-296, 06 2005. doi: 10. 15617/ RSS.2005.1.038.
S. Akhlaghi, N. Zhou, and Z. Huang. Adaptive adjustment of noise covariance in kalman filter for dynamic state estimation. In 2017 IEEE Power Energy Society General Meeting, pages 1-5, 2017. doi: 10. 00.1109/EESGM.2017 007775277755
Marcin Andrychowicz, Anton Raichuk, Piotr Stañczyk. Manu Orsini, Sertan Girgin, Raphael Marinier, Léonard Hussenot, Matthieu Geist, Olivier Pietquin, Marcin Michalski, Sylvain Gelly, and Olivier Bachem. What matters on-policy reinforcement learning? a large-scale empirical study, 2020.
Zafer Aydogmus and Omur Aydogmus. A comparison of artificial neural network and extended kalman filter based sensorless speed estimation. Mcasurement, 63:152-158, 2015. ISSN
0263-2241. doi: http://ddaarr////oooooooeeeeuuue
URL https:/ //www
sciencedirect. cwm/co///oooooo..e htt.://www.....t..o.......oo.aaa
Yu-ting Bai, Xiao-yi Wang, Xue-bo Jin, Zhi-yao Zhao, and Bai-hai Zhang. A neuron-based kalman filter with nonlinear autoregressive model. Sensors, 20(1):299, 2020.
S. T. Barratt and S. P. Boyd. Fitting a kalman smoother to data. In 2020 American Control Conference (ACC), pages 1526-1 1226-1531, 1531, 2020. doi: 10.23919/ACC45564 20200666..2000999 9114455.
Alex Bewley, Zongyuan Ge, Lionel Ott, Fabio Ramos, and Ben Uperoft. Simple online and realtime tracking. 2016 IEEE International Conference on Image Processing (ICIP), pages 3464-3468, 2016. doi: 10.
S. Blackman and R. Popoli. Design and Analysis of Modern Tracking Systems. Artech House Radar Library, Boston, 1999.
W. Blanding, P. K. Willett, and Y. Bar-Shalon Multiple target tracking using maximum likelihood probabilistic data association. In 2007 IEEE Acrospace Conference, pages 1-12, 2007. doi: 10.1 N0.1109/AERO.22073333
Sebastian Bock and Martin WeiB. A proof of local convergence for the adam optimizer. 2019 International Joint Conference on Neural Networks (ICNN), pages 1-8, 2019. doi: 10. 1009/
BCCNN2201.88552235
B. Carew and P. Belanger. Identification of optimum filter steady-state gain for systems with unknown noise covariances. IEEE Transactions on Automatic Control, 1866):58--877, 1973. doi: 10.1109/AA..193.II 100420.
Chaw-Bing Chang and Keh-Ping Dunn. Radar tracking using state estimation and association: Estimation and association in a multiple radar system, 04 2019.
Zhaozhong Chen al. Kalman filter tuning with bayesian optimization, 2019.
S. Kumar Chenna, Yogesh Kr. Jain, Himanshu Kapoor, Raju S. Bapi, N. Yadaiah, Atul Negi, V. Seshagiri Rao, and B. L. Deekshatulu. State estimation and tracking problems: A comparison between kalman filter and recurrent neural networks. ICONIP, 2004.
Huseyin Coskun, Felix Achilles, Robert DiPietro, Nassir Navab, and Federico Tombari. Long short-term memory kalman filters:recurret neural estimators for pose regularization. ICCV, 2017.
URL htlp:tts::// //q thub. www eecie stmkf TCCV2017 1
10

---

Under review as a conference paper at ICLR 2022
Philip
Zhuang Dan Iter, Jonathan
Kuck. Target tracking with kalman filtering, knn
and
Istms, 2016.
URL http:///ee2...aaaaooooaaaaaaapoa
pdf
JP DeCruyenaere and HM Hafez. comparison between kalman filters and recurrent neural networks. [Proceedings 1992] LICNN International Joint Conference on Neural Networks, 4:247-251, 1992.
Patrick Dendorfer, Hamid Rezatofighi, Anton Milan, Javen Shi, Daniel Cremers, lan Reid, Stefan Roth, Konrad Schindler, and Laura Leal-Taixé. Mo(20: A benchmark for multi object tracking in crowded scenes, 2020. URL httttp::/mmtchhaaaaat http:///otccaaaccc weegeeeehhhleeeeeeeeemomoo net/data /ttp /MOT20/
Lichuan Deng, Da Li, and Ruifang Li. Improved IMM Algorithm based on RNNs. Journal of Physics Conference Series, 1518:01 2055, April 2020. doi: 10. 10.1085/1742-6596/15 /18/1/0120/5
Jacob Devlin, Ming-Wer Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, 2019.
Jimmy Ba Diederik P. Kingma. Adam: A method for stochastic optimization, 2014. URL https
serxiv.org/aba. 14122 6980
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph,
and Aleksander Madry. Implementation matters deep policy gradients: case study on ppo and trpo. ICLR, 2019, URL htt.ttts///ppeeeeiiiiee wtt.we.weeeedeeeeeeeeeeeee http:pddfddrrttteeeederdrrdreemt rtPB
n
Hai Dai, Hong wei Bian, Rong ying Wang, and Heng Ma. An ins/gnss integrated navigation in gnss denied environment using recurrent neural network. Defence Technology, 16(2):334 340, 2020. ISSN 2214-9147. doi: ott.p///wwc..c..eeacaaaaoaaaaaaa
011. URL https
www. www.ssciencd..rec..oo http://awwwc.cee//c///////eaatta
Benjamin Fehrman, Benjamin Gess, and Arnulf Jentzen. Convergence rates for the stochastic gradient descent method for non-convex objective functions. Journa of Machine Learning Research, 21
(136):1-4,, 2020. BRL[http:// .aaemnrrrrrgg/oog
636 html
B. Feng, M. Fu, H. Ma, Y. Xia, and B. Wang. Kalman filter with recursive covariance es- timation- sequentiallyy estimating process noise covariance. IEEE Transactions Industrial Electronics, 61((1)):253-6263, 2014. doi: 10. 10.1109/11E.2214233077
Simone Formentin and Sergio Bittanti. An insight into noise covariance estimation for kalman filter design. IFAC Proceedings Volumes, 47(3):2358-2355 2014. ISSN 1474-6670. doi: https://
0bh.:g//00.1822200044444----444 1003 016111 URL https::////. //www/ www. s sciencedi rect. com/ science/articee//pii////
19th IFAC World Congress.
C. CaG, H. Liu, S. Zhou, H. Su, B. Chen, J. Yan, and K. Yin. Maneuvering target tracking with re- current neural networks for radar application. 2018 International Conference Radar (RADAR), pages 1-5, 2018.
Chang Gao, Junkun Yan, Shenghua Zhou, Bo Chen, and Hongwei Liu, Long short-term memory- based recurrent neural networks for nonlinear target tracking. Signal Processing, 164, 05 2019. doi: (0.10166j.iggrr.2211.5...
Matthieu Geist and Olivier Pietquin. Kalman filtering colored noises: the (autoregressive) moving- average case. In MLASA 2011, pages 1-4, Honolulu, United States, December 2011. URL
https://hal. supelec. www.eee..rccciii archives ouvertes...
Gautam Goel and Babak Hassibi. Regret-optimal estimation and control.
arXiv preprint
arXiv:2106.1 12097, 2021.
Google Scholar. Citations since 2017: "a new approach to linear filtering and prediction problems".
2021. /tt.a///aaa/////.aaaaa.....o...a

---

Under review as a conference paper at ICLR 2022
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep Reinforcement Learning that Matters, arXiv preprint arXiv: 2017. URL https
//axxxivorg///aoolao httpxii..rrp//f//1703333 00w.0.09..66..... pdf
Sepp Hochreiter and Jurgen Schmidhuber. Long short-term memory. Neural Computation,
1997.
wtw.://eet.....eeeeee//eee/eeeee Long-Shorz Term- (eerm-Memory:
URL
R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 1985.
Jeffrey Humpherys, Preston Redd, and Jeremy West. A fresh look the kalman filter. SIAM Review, 54(4))801-823, 2012. doi: 10. 10.1 137/10099996
Ala A. Hussein. Kalman filters versus neural networks in battery state-of-charge estimation: A comparative study. International Journal of Modern Nonlinear Theory and Application, 2014.
Faisal Jamil al. Toward accurate position estimation using learning prediction algorithm in indoor navigation. Sensors, 2020.
S. J. Julier and J. K. Uhlmann. Unscented filtering and nonlinear estimation. Proceedings of the IEEE, 92(3):401 422, 2004. doi: 10. 1099//ROC..203..0 8.3141...
R. E. Kalman. A New Approach to Linear Filtering and Prediction Problems. Journal of Basic Engincering, 82(1):35-45, 03 1960. ISSN 0021-9223, doi: 10.1115/1.366552.. URL https
//doi.org/100 1ttp:/1...1111111111 3662552
Chanho Kim, Fuxin Li, and James M. Rehg. Multi-object tracking with neural gating using bilinear Istm. ECCV, September 2018.
Yaakov Bar-Shalom X. X.-Rong Li Thiagalingam Kirubarajan. Estimation with Applications to Tracking and Navigation: Theory, Algorithms and Software. John Wiley and Sons, Inc., 2002. doi: 10.1002/0471222277
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics guarterly, 2(1-2):83-97, 1955.
Tony Lacey. Tutorial: The kalman filter, 1998. URL hhttp://web.mit.tt k
.pdf"
S. Li, C. De Wagter, and G. C. H. E. de Croon. Unsupervised tuning of filter parameters without ground-truth applied to acrial robots. IEEE Robotics and Automation Letters, 4(4):4102-4107, 2019. doi: 1091/ 201...930000..
M. Linderoth, K. Soltesz, A. Robertsson, and R. Johansson. Initialization of the kalman filter without assumptions the initial state. In 2011 IEEE International Conference on Robotics and Automation, pages 4992-4997, 2011. doi: 10.1 10.1109/C 200.ICCAA.011.99966. 1.5979684.
Hu Liu al. Kalman filtering attention for user behavior modeling in ctr prediction. NeurlPS, 2020.
Huajun Liu, Hui Zhang, and Christoph Mertz. Deepda: Lstm-based deep data association network for multi-targets tracking in clutter. CoRR, abs/1907.099 009115, 2019, 9a. URI. wtt.htt:://aii...oo//
abs/1907. 09915
Jingxian Liu, Zulin Wang, and Mai Xu. Deepmit: A deep learning maneuvering target-tracking algorithm based on bidirectional Istm network. Information Fusion, 53, 06 2019b. doi: 10.1016/j. inffus.2019.06.001
E. Mazor, A. Averbuch, Y. Bar-Shalom, and J. Dayan. Interacting multiple model methods in target tracking: a survey. IEEE Transactions on Aerospace and Electronic Systems, 34(1):103-123, 1998.
R. Mehra. On the identification of variances and adaptive kalman filtering. IEEE Transactions on Automatic Control, 175-1175--14, 1970. doi: 10.1109/TAC. 1970. 1099422.
12

---

Under review as a conference paper at ICLR 2022
A. Paulo Moreira, Paulo Costa, and José Lima. New approach for beacons based mobile robot local- ization using kalman filters. Procedia Manufacturing, 51:512-515 519, 2020. URL https:/ /www sciencedirect. www/ wwwpecccceenccccieeeeeeeeeea http://eeee....tts/ssssee /tt.e///3331111211 (007779999999999 30th Interna- tional Conference on Flexible Automation and Intelligent Manufacturing (FAIM2021).
Dominic A. Neu, Johannes Lahann, and Peter Fetrke. A systematic literature review on state- of-the-art deep learning methods for process prediction. CoRR, abs/2101.09322 2021. URL
09320
Behnam Neyshabur, Srinadh Bhojanapalli, David Mcallester, and Nati Srebro. Exploring gen- cralization in deep learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and Garnett, editors, Advances in Neural Information Processing Systems. volume 30. Curran Associates, Inc., 2017. URL /tsptttps///poocccii.g..... new..eerieiinnnse.............. CC/
Brian Odelson, Alexander Lutz, and James Rawlings. The autocovariance least-squares method for estimating covariances: Application to model-based control of chemical reactors. Control Systems Technology, IEEE Transactions on, 14:532 540, 06 2006. doi: 10. 10.1009/CTT.2200586600
Sebin Park et al. Measurement noise recommendation for efficient kalman filtering over a large amount sensor data. Sensors, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035.
Curran Associates, Inc., 2019.
Dong-liang Peng and Yu Gu. Imm algorithm for a 3d high maneuvering target tracking. International Conference in Swarm Intelligence, pages 529-536, 06 2011. doi: 10.
José C. Pinheiro and Douglas M. Bates. Unconstrained parameterizations for variance-covaaiincee matrices. Statistics and Computing, 6:289-296, 1996.
Guy Revach, Nir Shlezinger, Xiaoyong Ni, Adria Lopez Escoriza, Ruud J. G. van Sloun, and Yonina C. Eldar. Kalmannet: Neural network aided kalman filtering for partially known dynamics, 2021.
B. Ristic, S. Arulampalam, and N. Gordon. Beyond the Kalman Filter: Particle Filters for Tracking Applications. Artech house Boston, 2004.
David E. Rumelhart et al. Learning representattonns by back-propagating errors. Nature, 1986. URL
https:// http:://wwwwww// nature http://aaaaaee.o/arra///////////
A. Sengupta, F. Jin, and S. Cao. A dnn-lstm based target tracking approach using mmwave radar and camera sensor fusion. 2019 JEEE National Aerospace and Electronics Conference (NAECON), pages 688-693, 2019. doi: 1O. 10.1 1.110AACCONN4441..0000 wwwp:/4411.2219.9900 2019.9058988 168.
Robert H. Shumway and David S. Stoffer. Time Series Analysis and Its Applications (Springer Texts in Statistics), Springer- Verlag, Berlin, Heidelberg, 2005. ISBN 0387989501.
Harold Wayne Sorenson. Kalman Filtering: Theory and Application. IEEE Press, 1985.
D. J. Thomson. Jackknifing multiple-window spectra. In Proceedings of ICASSP '94. IEEE International Conference Acoustics, Speech and Signal Processing, volume vi, pages VI/73- VI/76 vol.6, 1994. doi: 10. 10911S/// 199....9999999999
Ryan Tibshirani. Proximal gradient descent and acceleration, 2015. wtwpttts::/// www stat grad. pdd]
cmu cmu.edu: wtwpaantissscooooo httd::/:cyooottt/////oooooooee/e
Anastasios Tsiamis and George Pappas. Online learning of the kalman filter with logarithmic regret. arXiv preprint 2rXiv:2002.05141, 2020.
13

---

Under review as a conference paper at ICLR 2022
Koji Tsuda, Gunnar Rätsch, and Manfred K. Warmuth. Matrix exponentiated gradient updates for on-line learning and bregman projection. Journal of Machine Learning Research, 6334);995-1118, 2005. URL / mlr. wwtp://ggpppap... papers v6 wttp///tttssdaaaaaa// html
Israr Ullah, Muhammad Fayaz, and DoHyeun Kim. Improving accuracy of the kalman filter algorithm in dynamic conditions using ann-based learning module. Symmetry, II(1), 2019, ISSN 2073-8994. doi: 10.3390/syml 10100994. URL https:::: www. mdpi. wwtpcct.mmmmaee.e 09777388994/111//99
Ashish Vaswani et Attention is all you need. NeurIPS, 2017.
E. Wan. Sigma-point filters: An overview with applications to integrated navigation and vision assisted control. IEEE, pages 201-202, 2006. 10090 109NSSPW.2006.4778....
E. A. Wan and R. Van Der Merwe. The unscented kalman filter for nonlinear estimation. Proceedings of the IEFE 2000 Adaptive Systems for Signal Processing. Communications, and Control Symposium (Cat. No.00EX373), pages 153-158, 2000, doi: 10.1100/ASSPCC.2000.82222
Nicolai Wojke, Alex Bewley, and Dietrich Paulus. Simple online and realtime tracking with a deep association metric. In 2017 IEEE International Conference on Image Processing (ICIP), pages 3645-3649, 2017.
doi: TO. 109///IP..007..5.0 1297782969...
L. Zanni, J. Le Boudec, R. Cherkaoui, and M. Paolone. A prediction-erro covariance estimator for adaptive kalman filtering in serp-varying processes: Application power-system state estimation. IEEE Transactions on Control Systems Technology, 25()):1683-169,, 2017. doi: 10.1 1091/09T 2016.2628716.
Paul Zarchan and Howard Musoff. Fundamentals of Kalman Filtering: Practical Approach. Amer- ican Institute of Aeronautics and Astronautics, 2000.
Tianyu Zheng, Yu Yao, Fenghua He, and Xinran Zhang. An rnn-based learnable extended kalman filter design and application. 2019 18th European Control Conference (ECC), pages 3304-3309, 2019. doi: 10. 10.3991/EECC22199889999
Hui Zhong, Zaiyi Chen, Chuan Qin, Zai Huang, Vincent W. Zheng, Tong Xu, and Enhong Chen. Adam revisited: a weighted past gradients perspective. Frontiers of Computer Science, 2020.
14

---

Under review as a conference paper at ICLR 2022
CONTENTS
Introduction
Preliminaries: the Kalman Filter Algorithm
3
KF Optimization Using Cholesky Parameterization
Kalman Filter Configuration and Optimization: a Case Study
Neural Kalman Filter: Non-linear Prediction Helpful?
6
Related Work
7
Summary
Preliminaries: Extended
16
Problem Setup and Implementation Details
18
Cholesky Gradient Optimization
22
Related Work: Extended
22
Aervortiial Estimation vs. Optimization in the Toy Benchmark
23
Theoretical Analysis: Estimation vs. Optimization in the Presence of Non-i.id Noise
25
Generalization Tests: Training and Testing on Different Benchmarks
28
Sensitivity of KF-Optimization to Train Dataset Size
29
Optimized Kalman Filter for Video Tracking
29
J Optimized Kalman Filter for Lidar-based State Estimation in Self Driving
30
Neural Kalman Filter: Extended Experiments
31
On the Guarantees of Gradient-based Optimization
33
M Detailed Results
33
15

---

Under review as a conference paper at ICLR 2022
A PRELIMINARIES: EXTENDED
A.1 MULGI-TARGET RADAR TRACKING
In the problem of multi-target radar tracking, noisy observations (or detections) of aerial objects (or targets) are received by the radar and are used to keep track of the objects. In standard radar sensors, the signal of an observation includes the target range and direction (which can be converted into location coordinates x, y. 2), as well as the Doppler shift (which can be converted into the projection of velocity Up. Ug. Vs onto the location vector).
The problem consists of observations--raate trackers assignment, where each detection of a target should be assigned to the tracker representing the same target; and of location estimation, where the location of each target is estimated at any point of time according to the observations {Chang and Dunn 2019). In the fully online setup of this problem, the assignment of observations is done once they received, before knowing the future observations on the targets (though observations of different targets may be received simultaneously); and the location estimation at any time must depend only on previously received observations.
Assignment problem: The assignment problem can be seen as a one-to-one matching problem in the bipartite graph of existing trackers and newly-received observations, where the edge between a tracker and an observation represents "how likely the observation 2j is for the tracker trk,". In particular, if the lggikive-oogliikelhooodd used for edges weights, then the total cost of the match represents the total likelihood (under the assumption of observations independence):
(mmach)) =
Σ
-log -2gg((z)(rkk)) = -log
II
P(zy(trks)
(3)
Emarhh
Emath
The assignment problem can be solved using standard polynomial-time algorithms such as the Hungarian algorithm (Kuhn] 1955). However, the assignment can only be as good as the likelihood information fed to the algorithm. This is major motivation for trackers that maintain probabilistic representation of the target, rather than a merely point estimate of the location. common example for such tracking mechanism is the Kalman filter discussed below.
A.2 KALMAN FILTER
Kalman Filter (KF) is a widely-used method for linear filtering and prediction originated in the 1960s (Kalman 1960), with applications in many fields (Zarchan and Musoff| 2000) including object tracking (Kirubarajan 2002). The classic model keeps an estimate of the monitored system state (e.g., location and velocity), represented (which uniquely determine the PDF of the distribution). The mechanism (see Figure I alternately applies a prediction step, where a linear model x Fz predicts the next state; and an update step (also termed filtering step), where the information of new observation z is incorporated into the estimation (after a transformation H from the observation space to the state space). general, both models Fi, Hy can be time- dime-dependent, but in practice they often time-invariant, thus the notation is often simplified to F' and H.
the mean and covariance P of normal distribution
Note that KF compactly keeps our knowledge about the monitored target at any point of time, which allows us to estimate both whether a new observation corresponds to the currently monitored target, and what the state of the system currently is. However, KF strongly relies several assumptions:
1. Linearity: both the state- transition of the target ft and the state-observation transformation hy are assumed to be linear, namely, fax) F, and hz(z)) He æ. Note that the Extended KF described helow, while not assuming linearity, still assumes known models for transition and observation.
2. Normality: both Statettransiion and -bserrbbsevvttio are assumed to have a Gaussian noise with covariance matrices Q and R respectively. its uncertainty P also correspond to the mean and covariance matrix of a Normal distribution representing the information regarding the target location.
result, the estimates of the state x and
3. Known model: F,, Q H,, R are assumed to be known.
16

---

Under review as a conference paper at ICLR 2022
While F, and H, are usually determined manually according to domain knowledge, the noise model parameters R. Q are often estimated from data (as long as the the true states are available in the data). Specifically, they often estimated from the sample covariance matrix of the noise: R === Cou( - H, Q = Cov(AX) = [ov([ - F }+)
(Lacey 1998).
Two non-linear extensions of KF Extended Kalman Filter (EKF) (Sorenson 1985) and Unscented Kalman Filter (UKF) (Wan and Van Der Merwel 2000) are also very popular in problems of non-linear state estimation and navigation [Wan) 2006). EKF replaces the linear prediction (Fe) and observation (H₂) models with non-linear known models fr and h, and essentially runs standard KF diu
2f with the local linear approximations Fr de l He = de la., updating in every step t. UKF does whole distribution, since such
not pass the state distribution æ, through the motion equations distribution transformation is unknown for general nonlinear state- snte-trransiton. Instead, it samples sigma points from the original Gaussian distribution, passes each point through the nonlinear transition, and uses the resulting points to estimate the new Gaussian distribution. Particle filters go farther and not bother to carry a Gaussian PDF: instead, the points themselves (particles) can be seen as representatives of the distribution.
Whether linear or not, single simple model is hardly enough to represent the motion of any acrial target. A common approach to maintain a switching model that repeatedly chooses between several mode, each controlled by a different motion model. Common simple models the Constant Velocity (CV), Constant Acceleration (CA), and Coordinated Turn Left Right (CTL and CLR). Note that in all these models the prediction operator F is linear. A popular switching mechanism is the Interactive Multiple Model (IMM) (Mazor al. 1998), which relies knowing the transition-probabilttes between the various modes.
In addition the challenge of predicting mode-transitions, the standard models in often simple to represent the motions of modern and highly-maneuvering targets, such as certain unmanned acrial vehicles, drones and missiles. Many approaches have been recently attempted improve tracking of such objects, as discussed in Section D
A.3 FORMULATION OF THE KALMAN FILTERR MODEL FOR THE DOPPLER RADAR PROBLEM
Tracking targets from measurements of Doppler radar is one of the main applications studied in this work. The basic setup of the problem is defined in Section 4.1 The KF model corresponding to this setup, in terms of Equation D
is follows:
1
1
1
1
1
F =
H1 = H(X) =
(4)
1
uz/r xn/r xz/r)
where X = Iful (in the notation of Section 4.1 and r /
x?. That is, the motion
model is the standard constant-velocity model, and the observation model corresponds direct observation of the location coordinates and measurement of the radial component of velocity.
Both models (F,, H)) do not directly depend on the time. However, in contrast the formulation of Equation [ H (X) does depend on the unknown state X, and thus H(X) is unknown in inference time. That is, the observation model h(X) (XX) X linear anymore. The variants of the KF in Section handll this non-linearity follows:
1. EKF is inherently designed to handle such non-linear model using the approximation ((X) f X, where H V xx)(X) and X is the recent estimate of X.
2. KF: for the standard KF, we use the common trick of approximating (X) with H (2). where is the recent observation. That is, we replace the unknown location (T,, T2) in Equation 4 with the location coordinates of the observation (Zxy Zys z2), resulting in:
(2) =
Za/i 2y/F zali)
17

---

Under review as a conference paper at ICLR 2022
where F +2
+ We also implemented other approximations (c.g., X instead of 2), but they did not show added value for the KF baseline in our experiments.
The KF parameters Q and R. were tuned by either Method craoiis-estimaatinn or Method (filtering- errors optimization). Note that both methods are casily applicable to the non-linear setting:
1. Method 1 in Equation 2 we simply replace H, with the actual observation model (X) (note that X is available in the training data in our settings).
2. Method[ as before, we repeatedly run the KF and calculate the gradients of its loss. We simply use the KF (or EKF) implementation explained above.
A.4 RECURRENT NEURAL NETWORKS
Neural networks (NN) parametric functions, usually constructed sequence of matrix- multiplications with some non-linear differentiable transformation between them. NNs are known to be able approximate complicated functions, given that the right parameters chosen. Op- timization of the parameters of NNs is field of vast research for decades, and usually relies on gradient-basee methods, that is, calculating the errors of the NN with relation some training-data of inputs and their desired outputs, deriving the errors with respect to the network's parameters, and moving the parameters against the direction of the gradient.
Recurrent neural networks (RNN) (Rumelhart et al. 1986) are NN that are intended to be iteratively fed with sequential data samples, and that pass information (the hidden state) over iterations. Every iteration, the hidden state is fed to the next copy of the network as part of its input, along with the new data sample. Long Short Term Memory (LSTM) (Hochreiter and Schmidhuber, 1997) is an architecture of RNN that is particularly popular due to the linear flow of the hidden state over iterations, which allows to capture memory for relatively long term. The parameters of a RNN are usually optimized in supervised manner with respect training dataset of input-output pairs.
A.5 NOISE DEPENDENCE BY CHANGE OF COORDINATES
One of the violations of the KF assumptions in Section 4 is the non-i.i.d nature of the noise. The interest in this violation is increased by the fact that the noise is simulated an i.i.d manner, which makes the violation non-trivial to notice.
The violation caused by the difference of coordinates: while the state of the target represented in Cartesian coordinates, the noise is generated in spherical ones. As a result, spherical dimensions with higher noise are assigned to the same Cartesian dimensions in consecutive time-steps, creating dependence between the noise in these time-steps in Cartesian coordinates.
For example, consider a radar with a noiseless angular estimation (i.e., all the noise radial), and consider a low target (in the same height of the radar). Clearly, most of the noise will be in the XY plane both in the current time-steps and in the following ones (until the target gets far from the plane). In other words, the noise in the following time-steps statistically-depen time-step, and not i.i.d.
the current
B PROBLEM SETUP AND IMPLEMENTATION DETAILS
Code: The code for this work is available here and naturally contains implementation details that may be missing in the descriptions below.
Targets simulation: Our simulated dataset consists of episodes of tens to hundreds of seconds. Each episode contains around 20 targets. Each target appears at a certain point of time, has certain acceleration and speed ranges, and alternately performs straight motions (in constant speed with acceleration) and turns (horizontally or vertically) until it disappears. The time progresses in discrete time-steps of size dt. The space is assumed to be 3D and homogeneous (no ground).
The randomization in an episode is expressed through the number of targets, each target'ss 's acceleration and speed ranges, target appearing time, initial target state, number of turns, directions of turns
18

---

Under review as a conference paper at ICLR 2022
[0/100] 22 targets, 5<=t<=146
3000
2000
1000
11000
2000
-3000
-6000
4000
-2000
-2000
2000
2000
4200
6000
Figure 6: A sample of targets trajectories.
(left/righh/up/dowwn), length of turns, length of straight intervals, whether accelerating in straight intervals and what the acceleration is.
Every time-step, the radar generates detections of the available targets. Each detection contains location information (æ, y, 2) and a Doppler measurement corresponding to the the location vector. Each detection has additive i.i.d Gaussian noise in
Radar simulation:
projection of velocity spherical coordinates, i.e., range, azimuth, elevation, and Doppler. The radar itself is assumed to be singular point located in the origin (0, 0, 0). Recall that we assume homogeneous space with no ground.
Tracking test framework: The predictive models (trackers) can be tested in a mere prediction framework (where each target is tested by itself), or in full tracking framework (where multiple targets are tracked simultaneously). In the latter, we use a tracking system (solver) consisting of matcher and multiple trackers. Every time-step during test episode, the solver runs the following procedures:
Observe: receive observations from the radar.
2. Assign: use the matcher (based on the standard Hungarian Algorithm (Khhn 1955). with re- lation to the corresponding trackers' likelihood functions) to assign observations to trackers; create new tracker for any unassigned observation; and delete any tracker whose target was not observed for several time-steps.
3. Update: update the location estimation of the trackers using the newly-assigned observa- tions.
4. Predict: predict the target location in the next time-step (to allow more accurate assignment of the next batch of observations).
In the scope of this work we are mainly interested in the tracker module. Note that the tracker affects the matching accuracy through the likelihoods it feeds to the matcher; and affects the estimation accuracy directly in the prediction and update operations. To solve both matching and estimation tasks, the tracker is required to provide good probabilistic model of the target location (namely, PDF the location) in addition to a point estimate.
We measure the estimation accuracy using the standard Mean Square Error (MSE) of the target location after the update step. For matching accuracy, for each target we consider the tracker that covers most of the target's observations, and count the percent of observations assigned to that tracker.
19

---

Under review as a conference paper at ICLR 2022
Trackers: To support the procedures described above, tracker must implement prediction and update steps, as well as exporting the current point estimate of the target location and the likelihood of any observation whenever queried.
All the trackers in this work are conceptually based on Kalman Filter (described in Section A.2 following elements characterize the exact nature of the tracker:
The
1. KF/EKF: the difference is in the observation model H,, as explained in Section A.2
2. Coordinates for representation of the observation noise It: while we represent the state in Cartesian coordinates ((2, y, 2, U., vy. uz) and measure the errors accordingly, the natural coordinates for the noise of the radar spherical, as the observation errors simulated independently for range, azimuth, elevation and Doppler. In particular, in Carte- sian coordinates the errors are not independent, hence R is not inherently constant. When implementing R in spherical coordinates, we have to transform it to Cartesian coordinates every time-step according the recent observation.
3. Determining the noise parameters Q, R by estimation/ootinnzatto::: by estimation of the noise we mean Q= Cooo(+++ - F),,, R = Cov (Z HX+) over the training data {X,, Z.) By optimization we mean that E R-1x4 Q E R are intended to minimize the loss of the predictions over the training data. Note that in the optimization, we represent R, Q using lower-triangular decomposition so that both matrices remain SPD.
4. Acceleration prediction: replace the linear motion model Fx with Fz + 0.5a - dt², where is predicted using LSTM that receives the observations and estimated states recurrent inputs.
5. Q prediction: dynamically predict the motion model noise Q using an LSTM. We use the same LSTM as for a, except for the head layer that outputs Q itself. For simplicity, we assume that Q is diagonal when dynamically predicted.
6. R prediction:
dynamically predict the observation noise R using a neural network that receives the recent observations and estimated states as inputs. For simplicity, we assume that R is diagonal when dynamically predicted.
7. H prediction: the observation model Extended KF handles this through a linear approximation around the currently state x. By H -preddiction, we aim to learn to choose H dynamically in optimal way to improve the tracking errors.
h(x) of a radar is non-linear function of x,
8. - representation: KF assumes Gaussian errors (in prediction and observation), hence the distribution of the state is always normal, which is somewhat limiting. We try to represent the distribution as a mixture of Gaussians (i.e., a linear combination of few Gaussians). The Gaussians are intended to correspond to possible modes of motion (c.g., constant speed vs. turn), and thus can predict the dynamic acceleration (see above) differently from each other. In addition, the amplitude of each Gaussian (i.e., the probability assigned to it) is predicted every step along with the accelerations.
Optimization of the noise parameters (R, Q) was implemented as part of the Optimized Kalman Filter (OKF) described in Section This feature was found make the tracker both more accurate and more robust to design choices such as KF vs. EKF or coordinates of R as described above. A neural-network- -base Dynamic prediction of acceleration and noise was implemented as part of the Neural Kalman Filter (NKF) described in Section 5 The NKF architecture is also described in detail
in Figure 7
The last two features in the list failed to provide successful results: dynamic prediction of fl often yielded unstable predictions, and a mixture representation had insignificant effects on the prediction. Furthermore, beyond? 2 Gaussians in the mixture, it seemed that any additional Gaussian became practically inactive, with amplitude being constantly near zero.
B. TRAINING
Training data: A training dataset consists of targets, each consisting of a sequence of states (e.g., locations and velocities) along with sequence of observations. In particular, the target state
20

---

Under review as a conference paper at ICLR 2022
Predict
ag h G (xx,, Zz, he
1 x Fx2 + at (Ar)2
Pet1 = FP,p T + Q (xxx, Ze 11/))
x PP
t+1
Xt Pt
t t
Update
RS. h = R(xx ze, 12)
Zt
K = P. (HPPH + +R)
Xt = x KK - -Hx))
Pt = (1 (I- (1-K)P
Figure 7: The Neural Kalman Filter (NKF) algorithm Section The differences from Figure 1 are marked. G. Q, R are neural networks of the type LSTM, and h h" are their hidden states (more accurately, and Q are different heads of the same network, and thus share the same hidden states A²). In addition to the raw the networks are also fed with certain manually-crafted features (e.g., the projection of direction zi²))
the perpendicular
ground-trute truth is assumed be known and available to learn from. This can be achieved either by simulated environment or by internal targets sensors (e.g., GPS) in a controlled experiment in physical environment. Note that the training dataset considers the targets independently of each other, targets. Targets assignment
and does not refer to the notion of episodes with possibly-simuttnned in such episodes can be handled by the Hungarian algorithm as mentioned above. The test dataset differs from the training dataset in the seeds used to generate the trajectories and the observations, and certain experiments also in some configuration parameters such as the permitted range of acceleration.
Noise estimation: For models whose parameters are determined by noise estimation (e.g.. the standard KF), the training reduces calculation of R and from the data the sample covariance matrices (Equation 2). Note that {rx} and { from Equation 2 correspond to the states and observations mentioned above.
Optimization (error minimization): For models whose parameters are determined by optimiza- tion (e.g., OKF and NKF), we use the Adam algorithm (Diederik P. Kingma, 2014), implemented by the PyTorch package, with initial learning rate of 0.01 (reduced by 50% every 150 training steps) and no weight-decay. Every training epoch goes once over each training target. In the beginning of each epoch, batches of 10 targets are randomly drawn.
Every training step corresponds to a single batch, where the training loss aggregated additively over the targets in the batch and over the time-steps of each target. That is, for each target in the batch, we run the tracker on the target observations; after each observation receive the corresponding state estimate from the tracker; and add the corresponding error to the loss.
The explicit training loss is the Mean Square Error (MSE) the estimated location (which is part of the estimated state) after the update step.
In the case study experiments on the Doppler radar domain (Section 4). each benchmark included 1500 simulated targets for training and 1000 targets for testing. A single training epoch sufficient for convergence of the optimized models. The optimization lasted a few minutes per benchmark (scenario) for all the baselines in parallel (OKF, OKFp, ORKF, OEKFp).
21

---

Under review as a conference paper at ICLR 2022
C CHOLESKY GRADIENT OPTIMIZATION
Section discusses an efficient method to apply gradient-based optimization to SPD matrices, based on parameterization of the SPD matrix using Cholesky decomposition (Pinheiro and Bates, 1996). This section presents this method more formally.
We consider an objective function f(; A) to be minimized, where is the input and A E F=x= are parameters formed as SPD matrix. We define A(L) = L.I. and
if <
(L(O)), = Po(m-1)/044
=
0 (1-2)((-1))22
ifi>j
where 0 R=(x+1)/2 We also denote the optimization update rule by u(0,g), where are the current parameters and g is the current gradient. For example, for the classic gradient descent. u( = og. Using these notations, the optimization method becomes as simple Algorithm This algorithm (with Adam's 's update rule) was used for all the KF optimizations in this work.
Algorithm 1: Cholesky Gradient Optimization
Input: objective f: update rule u; data X; initial parameters 6g E [R 1)/2; Output: SPD matrix e R"x*; I - 0o:
for training epoch do for data sample in X do
g - V Vaf( A(L()))); 0 + g0,
Return A(L(O));
Note that the diagonal of ((f) could be replaced by any increasing positive transformation. In fact, could even drop the positive transformation and allow non-positive diagonal entries in L: this would only eliminate the uniqueness of the parameterization, and would allow A to be positive semi-definite.
D RELATED WORK: EXTENDED
Kalman Filter parameters tuning: Estimation of the noise parameters in KF has been researched for decades. A popular framework for this problem estimation from data of observations {z} alone (Odelson et al., 2006 Feng et al., 2014:|1 Park et al. 2019), since the ground-truth the states {x)} is often unavailable in the data (Formentin and Bittanti 2014). In this work we assume that the ground-truth is available.
Many works addressed the problem of non-stationary noise estimation (Zanni al. 2017 Akhlaghi ct al. 2017). However, as demonstrated in Sections in certain cases stationary methods are highly competitive tuned correctly even in problems with complicated dynamics.
Optimization of KF parameters with respect to tracking errors was already suggested in Abbeel et al. (2005), using method that avoids gradients computation. In practice, "optimization" of KF parameters with respect to the eтrors is often handled manually using trial-anderroo (Jamil et al. 2020), or using grid-search over possible values Q and (Formentin and Bittanti| 2014 Coskun et al. 2017). Alternatively, the optimization is often simplified by restricting Q and /2 to be diagonal (e.g., S,, see the experiments in Barratt and Boyd (2020) and Li et al. (2019). Formentin and Bittanti] (2014) pointed out explicitly that "since both the covariance matrices must be constrained to be positive semi-definite, Q and Rt are often parameterized as diagonal matrices".
Gradient-based optimization of SPD matrices in general was suggested in Tsuda et al. (2005) using matrix- cetrrx-exppoents, and also possible using projected gradient-descent (Tibshirani, 2015) both rely on SVD- SVD-decomposition. In this work, we apply gradient-based optimization using the parameterization that was suggested in Pinheiro and Bates (1996), which requires a mere matrix multiplication, and thus is both efficient and easy implement.
22

---

Under review as a conference paper at ICLR 2022
Neural networks for tracking: While comparison between RNN and KF goes back to DeCruye naere and Hafez 1992); Chenna et al. (2004), the contribution of neural networks to non motion tracking has been widely researched mostly in recent years, in the context of both radar and other sensors. Liu et al. 2019b) focus on an offline framework, where a bidirectional LSTT receives full, normalized trajectory as input, and improves the target locations estimations of a UKF in a 2-dimensional space. The LSTM is trained to predict the residual errors of the UKF. Kim et al. (2018) focus on a "near-online" framework, where assignment of observation is decided after looking ahead a certain number of observations. They operate in the visual domain, incorporate both visual and motion information together make decisions, and suggest new variant of LSTM, where the hidden state / interacts with the new input through the multiplication har rather than linear combination of the two, and thus can be interpreted
non-linear linear
dynamic model rather than hidden memory.
Gao et al. 2018) 8) focus on online framework, similarly to our work, where assignments and estimations are done immediately with the receipt of the observations. For the private case of a one-dimensional recurrent input signal, they use two LSTMs for estimation of the target location one for the prediction step and one for the update step- to achieve improved estimation, Gao al. (2019) expand this work and learn predict both the location estimate and its mime-dmmnsiioal) variance according to the negative-log likelihood loss, which yields similar accuracy but provides uncertainty estimation. Dan Iter (0166) consider online tracking of single vehicles the 2-dimensional video screen a vehicle camera (the KITTI object tracking benchmark). Since they assume zero observation error, they focus on prediction error optimization. Their LSTM yields better point-prediction than KF, but does not improve the end-to-end tracking, which they hypothesize that could be caused by insufficient uncertainty estimation. Coskun al. (2017) suggest combination of LSTM and KF for the task of human pose estimation, learned on basis of the square estimation-errors. In particular, three LSTM modules are used predict the parameters F, Q, R of a KF.
Liu et al. 2 train an LSTM for data association. i.e., the assignment task. SSengupta et al. (2019) address the problem of sensors fusion using deep neural network. They incorporate information from monocular camera and mm mm Wave radar, and show how to handle failures in either of the sensors. Deng et al. (2020) consider standard models as building blocks for IMM, and replace the mode-transition matrix with an LSTM that estimates the transition probabilities dynamically, Peng and Gu (201T) replace the standard building blocks of IMM with modes that are dedicatedly-desiineee to track
targets.
combination of KF with attention models (Vaswani et al. 2017) was also suggested (Liu et al. 2020) in the context of click-through rate prediction in e-commerce, where vital information for prediction may be concentrated in certain time-steps on which the model should focus.
E THEORETICAL ANALYSIS: ESTIMATION vs. OPTIMIZATION IN THE TOY BENCHMARK
Section 4 demonstrates that the optimal noise parameters in KF often differ from the covariance of the noise. Here we analyze this effect for the private case of the Toy benchmark, where all KF assumptions (Definition 2.1 hold except for the non-linear observation model H(X).
Definition E.1 (The toy Doppler problem). The toy Doppler problem the filtering problem modeled by Equation with the system-state space X (I., y/ R, Ues Uy Wz) E RR and the following parameters:
1
1
1
1
F
H = H(X)
1
1
a/r y/r 2/r)
022
Q = 0 e pox6
o²
where /22 y2 22 and oz, Cy. oz, 0D 0.
23

---

Under review as a conference paper at ICLR 2022
As mentioned in Section 4 this toy problem is highly simplified. For example, the targets only move in exact straight lines, and the noise of the radar is drawn i.d in Cartesian coordinates. Yet, despite the major simplifications, we show below that the remaining violation of observation linearity leads to sub-optimality of noise estimation when determining the KF parameters.
Since the true X is unknown the KF in the inference phase, we assume that the KF approximates H (X) using H, which relies on the current estimates of z; y,
1
2/f 9/f 2/6)
Lemma E.1 (Effective observation noise in the toy Doppler problem). Consider the toy Doppler problem with the approximated observation model fI. At a certain time-step, assume that the positional estimation errors (i.e., the estimation errors of x, 2) are independent of the target velocity u. Then, the observation noise corresponding to H (the effective observation noise) is described by the following covariance matrix:
R
y
R +
(5)
0
o
C
C
for some C 0.
Proof. Denoting & == 2/r (and similarly for ÿ, 2), we can rewrite as
H
J dā 4+ 3 + dā
where dē, dý, dă are the corresponding (normalized) estimation errors. Note that in the private case where v. y, z are estimated by the observations 2z, Zy: 2z, these errors coincide with the corresponding entries of the observation noise (up to the normalization by r).
By shifting the observation model in Equation
from H to H, we receive
Va
Vx
H X iX
Vy
= - +
Vy
Vz
VD - dōu, djju, dzuz/
VD
di
that is, the observation noise corresponding to H is ū = (Vz, My, v/D - di u)
dē, Va are both independent of the velocity u, (the former by the lemma's assumption, and the latter by the model of Equation 1 in Definition E. Thus, Corr uzz Mx) = E(dē vx) F(dāvv))F(u 0, and similarly for Vy, Vz. Hence, by denoting C (dr u) > 0. the covariance matrix of i/ is indeed R.
Lemma provides the theoretical explanation for Figure 4b in Section where we see that the optimization of Rt increases the variance of the Doppler signal compared to the variance of the positional signal. Figure 4b also shows decrease in the positional variance (not only an increase in Doppler's variance), which is not explained by the analysis above. This is caused by the fact that when = the absolute values of R have quite minor importance compared the relative values between the components hence the optimization increases Doppler's variance compared to positional variance, but quite indifferent their scale. Indeed, re-scaling of the optimized provided indistinguishable empirical results.
Note that this private case of Toy benchmark, the gap between estimation and optimization could be easily solved by modifying the estimation from R == Cov(1z, [xx)) xx3)) to R = Cou( - (2,) ) 223). However, this correction does not guarantee optimal results beyond the Toy benchmark, and in particular did not demonstrate significant improvement in the other benchmarks defined in Section 4 Indeed, while certain private cases can be modeled and solved analytically through effective noise estimation, optimization of the parameters provides more robust solution.
24

---

Under review as a conference paper at ICLR 2022
F THEORETICAL ANALYSIS: ESTIMATION vs. OPTIMIZATION IN THE PRESENCE OF NON-I.I. NOISE
The KF model assumes i.d noise for both the motion model and the observation model. In cases where the noise is known follow another specific model, dedicated solution sometimes be developed. For example, if the noise is auto-regressive with a known order p. an adjusted KF model may consider the last p values of the noise itself as part of the system state (Geist and Pietquin 2011). However, we often do not know the actual model of the noise, or we do not know how to develop the corresponding analytical solution, In any of these cases, the default practical choice is to keep the original KF model. However, the covariance matrices of the noise are not guaranteed anymore be the optimal values of the KF parameters Q and R.
aware all of the violation of the i.i.d assumption.
For example, consider the problem of moving target two-dimensional space, with observation noise drawn i.i.d in polar coordinates (similarly to the lidar model of Appendix D.. For simplicity of the analysis we represent the state using only the location x = (x1, x2) IR, and assume a model of no-motion up to an isotropic noise. Furthermore, we assume that the observation noise has only radial component.
Definition F.1 (The simplified lidar problem). The simplified lidar problem is the filtering problem modeled by Equation with the following parameters:
F= = H 0
rro 0
0)
Q =
Repotrr
where the observation noise P is drawn i..d from (0, Rpolar) in polar coordinates. We also assume that the initial system-state zo is drawn from an isotropic distribution, i.e., follows a density function of the form f(zo)) / (xo)2), which invariant the target direction.
for some 9,
At a first glance, this simplistic problem may seem to satisfy the KF assumptions. In particular, both sources of noise are i.i.d. However, the observation noise is drawn i.i.d in polar coordinates, while the system state estimated (and the prediction error measured) in Cartesian coordinates. As discussed in Appendix A.5, the i..d property is not invariant to the coordinates transformation!
Lemma F.1. The observation noise in the simplified lidar problem is noti. in Cartesian coordinates.
Proof. Denote the system state at time by x; = ((x)),, (xt)2) T and denote lan 0 = ((x))2/(x)) (x)) From Definition E1 by direct coordinates transformation, the observation noise drawn from the distribution U/ N (0, R())), where
To cos (0) cos(O) sin
To cos sin(O) To sin (0)
R())-
This noise covariance matrix varies every time-step with 0, hence the noise D, is not identically- distributed in Cartesian coordinates. Furthermore, consecutive time-steps are likely have similar values of (according to the motion model), hence the noise is not independent either.
If we are aware of the particular noise model of the problem, we can estimate Rpolar in polar coordinates and transform it to the Cartesian R(0) dynamically every time-step (e.g., using our the current estimate of 6, since the 0 unknown). This is indeed what do the KFp model in Section If we are not aware, however, we would simply estimate constant covariance matrix R in Cartesian coordinates.
Lemma F2 (Noise estimation in the simplified lidar problem). Let R be the sample covariance matrix of the observation noise, calculated by Equation 2 with respect to dataset of i.i.d targets in the simplified lidar problem. Then, as the number of targets in the data grows, R converges almost surely to
Rest (To/2
/ro/2
0
ro/2
25

---

Under review as a conference paper at ICLR 2022
the distribution of the initial system-states is isotropic, and so is the motion model Q. Hence, for any target at any time-step, the distribution of its direction (where tan 0 ((z))2(<x))) )) follows the uniform distribution: 0 [0,2x). Now calculate:
Proof. From Definition F.1
2t
Eo (Rest))1] Eg (ro cos? 0]
cos
0d0
2
2x
To
Eo (Rest)22l Eg [ro sin 0]
sin
Ade
2x
2m
To
Es ((e = Eo (Rest) = Eg (ro cos 0 sin 0
Jo
cos 0 sin 0dd = 0
2n
and since the targets are i.i.d, by the Law of Large Numbers we have
R as.
Rest
(ro)
(ro/2 0 ro/2
So far that the actual observation noise is R(0) (where 9 changes every time-step), while the constant covariance matrix that would be obtained by noise estimation is (asymptotically) Rest- Assuming that constraint ourselves to constant matrix (invariant 0) in Cartesian coordinates, can we do better than Rest? More specifically, due to the radial symmetry of the problem, we can denote w.l.o.g
0
Rope(r) = 0
for some > 0, and ask what value of r would result in minimal square filtering errors of the KF.
Lemma F.3 (Optimization the simplified lidar problem). Assume that at a certain time-step in the simplified lidar problem, the state of the system is known to be normally-distriuus with mean and covariance
Po = (
z0 = (x1,
and that a new observation = (x) + d + do2) T is received. Denote by the point-estimate of the KF following filtering step with respect noise parameters of the form Rope (r). Then, pro 2p+ro minimizes the expected square error (MSE) of z. Furthermore, (Ropt) = = < (Rest)s (for E 21, i.e., the optimal value of is smaller than the value obtained by noise estimation.
Proof. As the true model of the observation noise R(0). by applying the KF update step (specified in Figure D obtain the new true mean of the system- state distribution:
Fo + POH (HPOH + R2 Hoo) = + Po (2-
Strue
To sin" 8+p
cos Psind
dr
+
(To sin? 0+p)dar - (ro sin d)
-o +
p+rro
ptro To cos 8+p
ptro (ra cos" 0+p)dz (mn cos siu ddz,
eos A sin
dxz
+
P-
ptro
p
where 9 corresponds to the (unknown) true direction of the target. However, due to the restricted form of Rope (r) (which is independent of 0), the actual estimate would be
(x1 + p
da + P dxa)
The expected error of the point-estimate be decomposed into two terms: the bias of x. and the variance the system-state distribution. More formally. we can write MSE -SE (Parue) M F (I, Itrue), where can only control the latter. Specifically, denote a(r) p/ (p +
26

---

Under review as a conference paper at ICLR 2022
and look for the value of that minimizes the MSE. We use the identities sin 26 cos @ sin @ and E [zff] = E [zž = q (the latter is by the motion model in Definition F.1)
M ESiisia (I(a),
Eliz Zerue 11
(a rosinn 0 0+1 )dx +
2
E
dx2
p p+ ro
p+ To
cos 0 +
sin (20)/2 dx1
27
+
(a
dzz
p+ prro ro
p p+ ro
To sin 0 ++P a² 2a
ro Aisin2(22 (20)/4
d
+ +G1
dx² + A A1dx dx2
p+ ro
(p+ rr))
ro cos² p + C2
r sisn2((0)) (20)/4
+ dx
a² 2a
dx + Andrido2
p+ ro
(p + ro)²
To + 2p
rū sin (20)/2
=2ga²
2ga
+ q(C C2) +
p + ro
(p + ro)²
where C1.2 are independent of and 1,2 are multiplied by 1(d2) = 0 and vanish. To minimize we calculate
dMS Ebiso (z(a), Itrue)
2p + To
0
4q 24
da
which gives us
+ ro/2
p+ ro
Note that the expression of MS Edine above clearly diverges as |a| 0o, hence the only critical point necessarily corresponds to a minimum the MSE. Thus, the optimal MSE given when substituting the following r in Ropt:
p/a- p= 1² + pro (p² pro/22
pro
p p+ p
2p + ro
For the last part of the lemma, we recall that (Rest)i )a = ro/2 and compare r directly:
(Rest)is - (Ropt)is = ro/2 r-= (pro rr//2) pro
///22
> 0
2p rn
2pp + ro
Lemma F.3 shows that independently of the value of 4o (i.e., independently of the current state of the system or the current direction of the target), the expected filtering error would benefit from reduction of the noise parameter to (Ropt)) ) < (Rest)st Hence, noise estimation is not an optimal strategy for parameters tuning in this problem.
The simplified lidar problem can be seen as simplification of the problem experimented in Ap- pendix [] with a degenerated motion model. In the experiments, the optimization the KF reduced the .MSA E by 14.9%, and the learned parameters indeed decreased the observation noise, as shown in Figure
In summary, in this section we introduce simplified lidar problem. While at first glance the problem seems to follow the KF assumptions, the i.i.dnnoise assumption is in fact violated by the natural polar coordinates of the sensor. Consequentially, the optimal values of the R parameters do not correspond anymore to the covariance of the observation noise, but rather should be reduced. In other words, the non-i.i.d nature of the noise reduces the effective noise. This theoretic result is consistent with the experiments presented in Appendix[]
27

---

Under review as a conference paper at ICLR 2022
[Lidar]
(Lidar]
[Uidar]
[Lidar]
y
y
y
vy
Y
vy
26
00
26
-1
12
51 23 0
43
24
-1
49
157
Figure 8: The observation noise (It) and prediction noise (Q) matrices obtained by noise estimation (KF) and by optimization (OKF), for the problem of state-estimation from lidar measurements (described in Appendix D
G GENERALIZATION TESTS: TRAINING AND TESTING ON DIFFERENT BENCHMARKS
In the case-study of Section we demonstrate the robustness of an Optimized KF (OKF) over variety of benchmarks representing different tracking scenarios where in every benchmark, OKF (Method obtained lower estimation errors than a standard KF (Method [ over an out-of- sample test data. This demonstrates that OKF did overfit the training data, but still relies representativeness of the training data, i.e., on the assumption that the training data and the test data taken from the same distribution.
A stronger generalization ability is demonstrated in Section S where OKF beats both KF and NKF only on out-of-sample test data with the same settings, but also a test data with different settings. Specifically, we consider changes of factors 0.5 and 2 in the scale of the targets acceleration. This essentially changes the motion of the targets, including turns sharpness, speed changes and typical scale of speed. In terms of the linear motion model of KF, the acceleration corresponds to the motion noise Q, hence we essentially changed the noise after had been learned, which poses significant gencralization challenge. Thus, the results of Section provide a significant evidence for the robustness of OKF to certain distributional shifts.
LLS
.20
Bile
3.00
3.55
2.04
1.77
Ohice
3.67
12.35
Chic
5.14
11
330
1.0
3.55
4.00
1.99
(a) MSErratio MSE(KF) MSE(KF)/MSE(OK ((KKF for every Ka-blleline (KEKFP.EKF.EKFp defiend Sec- tion and every pair train-scenario test-scenario. The colormap logarithmic (~ log ratioa) where red values represent advantage to OKF (MSE ratio > 1).
Generalization between scenarios
log( MSE(est) MSE(opt)
10
train scenario
0.8
Close
0.6
Const
Free
-0.2
KFP
EKF
EKFp
variant
(b) For every train-scenario M Earaio is averaged over all the test-scenarios and is shown in a logarithmic scale. Positive values indicate advantage OKF
Figure 9: Generalization tests: optimization vs. noise estimation under distributional shifts.
In this section we present a yet stronger evidence for the robustness of OKF not over a para- metric distributional shift, but over entirely different benchmarks. Specifically, consider the
28

---

Under review as a conference paper at ICLR 2022
5 benchmarks (or scenarios) of Section 4 For every pair (train-scenario, test-scenario), train both KF and OKF on data of the train-scenario, then test them on data the test-scenario. For every such pair of scenarios, MSE ratio = SSE F) F)/MSF(OK
measure the generalization advantage of OKF over KFF through
(where MSF ratio > indicates positive advantage). calculate To measure the total generalization advantage of model trained certain scenario, the geometric mean of MSE Fatio over all the test-scenarios (or equivalently the standard mean over the logs of the ratios). Note that the logarithmic scale is indeed more natural for a symmetric view of the ratio of the two MSE scores.
This test is quite noisy, since model optimized for certain scenario may legitimately be inferior in other scenarios. Yet, considering all the results together in Figure 9 it is evident that optimization of KF yields more robust models in most cases, and even when it is inferior to noise-estimation, it does not lose by a large margin.
H SENSITIVITY OF KF-OPTIMIZATION TO TRAIN DATASET SIZE
Each benchmark in the case-study of Section has 1500 targets in its train data. Training from these datasets demonstrated significant advantage optimization of KF over noise-estimation. However, one may argue that on smaller datasets, optimization may struggle harder than noise-estimation, e.g., due to numeric instability with little data. Furthermore, the standard optimization procedure "wastes" a portion of the train data as a validation set, which does not contribute directly to the training, and thus may increase the sensitivity to the amount of data.
To test the sensitivity of KF optimization to the amount of data, we repeated some of the tests of Section 4 Jusing smaller subsets of the train datasets beginning from as few as 20 targets per dataset. Figure 10 demonstrates that the advantage of OKF over KF holds consistently over the various sizes of the train datasets, although indeed increases with the amount of data. In fact, in the Free Motion benchmark, the state-estimation errors of the standard KF monotonously increase with the amount of data.
Const
15000
model
model
KF
OKF
20000
OKF
KFp
13000
OKFp
MSE
18000
OKFp
12000
16000
11000
14000
10a
10a
10
train samples
train samples
Figure 10: The advantage of OKF over remains positive - although sometimes smaller - even when the train data reduces to as few as 20 targets. The shadowed areas correspond to 95% confidence-interven
I OPTIMIZED KALMAN FILTER FOR VIDEO TRACKING
Radar tracking is an interesting domain with unique properties such as non-linear observation model and radial observation noise. In this domain, Section 4 demonstrates the sub-optimality of KF with estimated noise parameters, compared to KF with optimized parameters. In this section, we compare the two in the popular and arguably-simpe domain of video tracking, using the MOT20 dataset (Dendorfer et al. 2020) (available under Creative Commons AtributionnNNnCoommerrco ShareAlike 3.0 License).
MOT20 includes several videos with multiple targets (mostly pedestrians) to track. The dataset also includes the ground-truth location and size of the targets in every frame the videos. We consider these ground- -ruth states direct observations, i.e., assume have detector with observation error (which in particular makes the observation model linear, in contrast to the radar tracking problem).
29

---

Under review as a conference paper at ICLR 2022
More specifically, characterize target using the state X (a, y, w. h, ux. vy) R (two- dimensional location, size and velocity), and an observation as Z = (a. y, w, h). Note that z, y, w, provided in the dataset and derive vz, vy from z, y. The observation model H is known as described above, and for the motion model F we assume constant velocity and constant target size, leading to:
1, 0, 0, 0, 1,
0, 0,
0, 1,
0, 0,1,0,0,00
0,0, 1,0,1,00,00
F
0,0, 0,0,
0, 0,0,0,0,,00
0,0 0,0,0.1.0. 1,0,0
0, 0,0,0.0.1.0
0,0,0, 0,0,0,
Q and R are estimated optimized with relation the train data, as described in Section 4 For the and for the test data MOT20-05, In particular, test data comes from entirely different video than the train data, hence the testing is less prone to overfit. The goal function for the optimization is the MSE (mean square error) the location æ, after the prediction step (note that in absence of observation noise, the error of the update step simply zero).
train data we use MOT20-01, M0120-00,,00220002220 -M0020002.M0T200-
As shown in Figure the optimized model (OKF) reduces the prediction errors (MSE) by 18% in comparison to a KF with standard noise estimation. The significance level of the results is 125, corresponding the errors difference (calculated as / / samppies) The results indicate that the sub-optimality of noise estimation as well as the benefits of parameters optimization are cross-domain phenomenon and not limited radar tracking to non-linear observation models.
also indicated by the huge z-value mean Aerr) / (st((Aerg)
1
ground
OKF
MOT20-05: RAW
Figure 11: A sample of targets in the first frame of the test video in MOT20. The true trajectories of the targets shown along with the predictions of KF and OKF (each prediction done time-step advance).
J OPTIMIZED KALMAN FILTER FOR LIDAR-BASED STATE ESTIMATION IN SELF DRIVING
Another domain in which we test the Optimized Kalman Filter (OKF) of Section 4 state- estimmattin in self-driving based on lidar measurements with respect to known landmarks (Moreira et al.; 2020). For simplicity, we focus on location estimation and on a single landmark (as the matching problem from multiple landmarks is out of the scope of this work).
30

---

Under review as a conference paper at ICLR 2022
We formulate the problem follows: the target state is X (z. U.z, vy) E IR (two-dimensional location and velocity), and an observation is Z = (z. y). The dynamics are simulated as follows: each target trajectory consists of several intervals, in each one the target has certain (positive or negative) acceleration and certain lateral acceleration ("turn magnitude"), both drawn randomly at the beginning of the interval. The observation noise is drawn i.i.d in polar coordinates. We simulated corresponding dataset of 2000 targets as demonstrated in Figure 12a and split them to train set (1400 targets) and (600 targets).
From the KF point-of-view, the dynamics and observations are modeled by:
1,0,1,0
1,0,0,0 H 0, 0,1,0,0
0, 0,1,0,1
F=
0,0,1,0
0,0,0,1
Note that the lidar problem is inherently different from the radar problem (Section 4) since the observation model linear (due the absence of the Doppler signal); and is different from video tracking (as formulated in Appendix[] since the observations are not assumed to be noiseless. On other hand, similarly to the case of the radar, the Cartesian representation of the observations prevents their noise from being i..d, since the observation noise is only i.i.d in polar coordinates (see Appendix[A.35
We trained the OKF of Section 4 with respect to the MSE of the estimated target location, described in Appendix [.I and trained a standard KF by estimating the noise as Equation 2 Then we tested both models the test data. The optimization significantly reduced the errors by 14.9%, as shown in Figure [2b This joins the promising results from the two other domains (radar tracking and video tracking), and demonstrates the generality of our method.
Lidar prediction-ente
Mete32
(Normalized z-value for (KF-OKF): 54)
1500
(dashed-mean)
OKF (dashed-mean)
30
-100
-000
-200
ground-truth
10
obuer valion
-162
3.51
1946
quantile
(a)
(b)
(c)
Figure 12: (a) A sample of targets trajectories from the simulated self-driving data. (b) Prediction errors of KF and OKF on 600 targets of the test data. OKF is clearly more accurate, as also indicated by the huge z-value corresponding to emrors difference (calculated = = mean (Aerr) / //ddd(((rr (eerr) /N). (c) tracking of KF and OKF on sample target trajectory, focused on the time interval 14 t 32 for visual clarity.
K NEURAL KALMAN FILTER: EXTENDED EXPERIMENTS
Section 5 demonstrates that even if a neural-network (NN) based model provides more accurate predictions than a standard KF - its advantage may be entirely vanished when compared to an optimized KF instead. It is shown for the specific NKF model Doppler radar problem. This is sufficient to demonstrate the error in the common methodology that compares optimized NN-based models non-optimized variants of KF.
free-motion benchmark in the
To show that these results are not exclusive to the experiments of Section 5 we present extended experiments in this section. Specifically, we consider 2 different benchmarks - the free-motion benchmark of Section 5 and Const_a benchmark of Section 4 (in which the targets may have acceleration but not turns). We also consider different neural models:
KF (aKF): variant of NKF without dynamic prediction of the covariance matrices Q and R in every step (in terms of Appendix [ a tracker with elements 3, 4).
31

---

Under review as a conference paper at ICLR 2022
Neural KF (NKF): the model used in Section | and shown in Figure 7 (in terms of Ap-
pendix a tracker with elements 4, 5, 6).
Neural KF with H-prediction (NKFH): a variant NKF that also predicts the observation model H dynamically in every step (in terms of Appendix B tracker with elements 4, 5, 7).
For each benchmark and each model, trained the model train data with certain range of targets acceleration (note that acceleration affects both speed changes and turns sharpness). and tested smaller
it targets with three different acceleration ranges the original one. That is, some of the test datasets correspond to distributional shifts. For each model we train two variants- representation (as in the baselines of Section[4] 4 and we select the best among the two variants using the MSE scores on the validation data (which portion of the data assigned for training).
and larger
with Cartesian representation of the observation noise R, and one with spherical
We measure the results using (1) the Mean Square Error (MSE) of the estimated location after each update step: and (2) the
(NLL) of the the estimated state-distribttio. after the prediction step. Note that NLL is important for matching observations to targets in the multi multi-target tracking problem (which is out of the scope of this work).
system-state with relation to
SM baseline)
1000
ANLL (wrt KF baseline)
35
499
12. H
12 2.99
12.9k
13.2K
12.9K
13.1
16.1K
-2000
OKF
12.
14 SK
OKF
-3000
NKF
13.75 7K
13 .3.8K|
NKF
NKFH
NKPH
-4000
12<acc=24
M4cacc<48
#8accc99
12<scc=224
24<acc<488
48<acc<96
(a) Free-motion benchmark
(wrt KF baseline)
-1000
66
10.8k
10 10.6K
11 oxt
ANLL (wrt KF baseline)
10.
-2000
111
10.5K
-3000
10 aK
OKF
OKF
-4000
aXF
aCF
NKF
694
J L
NKF
X
1Q
-5000
NKFH
NKFH
04<accc008
08<acc<<16
16<acC<32
04<acc<008
08<acc<16
16<acc<<32
(b) Consta benchmark (no turns)
Figure 13: The relative MSE and NLL results of various models in comparison the standard KF model. The textual labels specify absolute MSE NLL. Note that certain bars NLL are entirely different scale and thus are cropped in the figure (their values can be seen in the labels). In each benchmark, the models were trained with relation MSE loss, on train data of the middle acceleration-range the two other acceleration ranges in each benchmark correspond to generalization
distributional shifts.
Figure 13a shows that in the free-motion benchmark, all the 3 neural models improve the MSE in comparison to a standard KF, but lose to an optimized one (OKF). Furthermore, while OKF has the best NLL scores, the more complicated models NKF and NKFH increase the NLL in orders of magnitude. This issue may be handled by explicitly optimize the NLL in addition to the MSE, but such multi-loss optimization is out of the scope of this work. Note that the instability of NKFH is expressed in poor generalization to lower accelerations in addition to the extremely high NLL score.
Figure 13a shows that in Const_a a benchmark, all the neural models improve the MSE in comparison to standard KF, but only NKFH improves in comparison to OKF as well. Note that while NKFH does better in this case than in the free-motion benchmark, it still suffers from very high NL...
32

---

Under review as a conference paper at ICLR 2022
In summary, by comparing the optimized neural models to the standard KF model, all the models would be found superior to the KF in both benchmarks in terms of MSE. However, when shifting the baseline to optimized KF,, find that the neural aKF and NKF are in fact inferior to OKF, and that the comparison between NKFH and OKF depends on the selected benchmark and metric.
Of course, results do not imply that neural-networks in general cannot be superior KF: only that when comparing the two, one must optimize the KF similarly to the neural model to avoid misleading experimental results. As discussed in Section 6 the wrong methodology of using non-optimized KF baseline is very common in the literature.
L ON THE GUARANTEES OF GRADIENT-BASED OPTIMIZATION
Method 2 can rely on any gradient-based optimization algorithm, such as SGD or Adam (Diederik) Kingma 2014) (the latter is used in this work). Such optimization algorithms have achieved remark- able results in variety of optimization problems in the recent years. This includes impressive results non-convex problems where local-minime exist (Zhong al. 2020 as well as generalization to unseen data (Neyshabur et al.) 2017).
Compared to the problems where algorithms like Adam are often applied (e.g., language models with more than 100M parameters (Devlin et al. (019)), typical filtering problems such as the ones experimented this work are arguably small and simple to optimize. Thus, the robust results of Method namely, the consistent advantage over Method] [ in all the experiments in this work should not come as a surprise.
Having said that, the theoretical guarantees of the gradient- basee algorithms are limited for non- convex problems. Note that the dependence of our loss function (filtering errors) on the model parameters (after the Cholesky parameterization) is indeed not convex. In such settings, convergence to local optimum of the loss is in fact guaranteed: Adam, for example, is guaranteed to converge given a wice-differentiable loss function (Bock and WeiB 2019). Stronger convergence guarantees exist for the SGD algorithm under certain conditions (Fehrman et al. 2020), yet in general, gradient- based optimization algorithms do not necessarily converge to the global optimum of the loss.
Note that in all the problems experimented in this work, the standard Method [[mois--sttimaton) has optimality guarantee either, as the KF assumptions do not hold. Indeed, the experiments demonstrate its sub-optimality, and Appendices F prove it theoretically for sample of problems.
M
DETAILED RESULTS
Figures 14 17
below provide additional details about the experiments discussed in Sections 5
33

---

Under review as a conference paper at ICLR 2022
15000
KFp
10000
OKF
5000
OEKF
OEKFp
104
Close
Const
Const
Ree
(a)
2.2
2.0
3.6
3.0
(b)
Figure 14: (a) Errors of different tracking models different benchmarks. This is different visualization of the results of Table The error-bars correspond confidence intervals of 95%. Note that the optimized models (the last four) tend to yield better and more stable results than estimated models (the first four). (b) The RMSE ratio between the estimated models and the optimized ones, over all the henchmarks and designs discussed in Section 4 Note that all the ratios above 1, i.e., all the models in all the benchmarks had smaller emrors when tuned by optimization. The horizontal line represents the average ratio.
[Tree] RR
["rea] OKF /R
7
48bu
4190
39
34000
-0
198
310
45387
-22
-364
15810
4300
319
0
25
29
(a) R (estimated)
(b) It (optimized)
(c) Q (cstimated)
(d) Q (optimized)
Figure 15: The observation noise (R) and prediction noise (Q) matrices obtained in (Cartesian) KF by noise estimation and by optimization with relation to M MSE. based on the dataset of the Free-motion benchmark.
Close
Const a
1500
3000
2500
300
-3000
4000
-7200
-0000
-4533
-2000
X000
4000
0000
Figure 16: Samples of targets trajectories in the various benchmarks described in Section projected onto the horizontal plane. This extension of Figures 2b for the rest of the benchmarks.
34

---

Under review as a conference paper at ICLR 2022
20000
303
15500
konghh
153
101
cosol_5
Covet
Fiae
10
CUSO
Conet
Fre0
105
Opvet
Free
175
110
303
70
333
vol
Orsa
condl
Corsl_t
Pant
70g
Rren
10l
(164
Figure 17: Descriptive statistics of the various benchmarks of Section duration of targets trajectories; distance from the radar; targets speed; targets acceleration; motion direction (90 degrees correspond to horizontal motion); and observation
distance from radar.
35


Reviews:
[{"review_id": "rCg2w3aSiKW", "reviewer": "Reviewer_D5C1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n+ The problem of estimating state from noisy observations for nonlinear systems is an open and important challenge, and the proposed method is intuitive and simple to implement, and appears to yield good empirical performance.\n\n+ The paper is clearly written and easy to follow.\n\n+ The empirical evaluations are comprehensive, in that many scenarios and baselines are considered.\n\nWeaknesses\n\n- Some of the more minor contributions are in fact well established.  While I completely agree that highlighting the shortcomings of the Kalman Filter in an expository manner provides excellent motivation for this work, the idea that state-estimation was a solved problem since Kalman and that the paper is reopening this solved problem is incorrect and a bit over the top.  That the Kalman Filter is only optimal under strong assumptions, and that it can fail spectacularly when these assumptions are violated, is very well known and hardly a contribution. Similarly, using a Cholesky parameterization for optimizing over PSD matrices is standard.  In light of this, I would recommend that the grandiose tone taken in the introduction perhaps be pared back a little bit, as I found it distracted from the otherwise nice insights of the paper.\n\n- Definition 2 is formulated under the assumption of a linear-time-invariant system; however, Kalman Filtering approaches in the time-varying setting also exist, see for example the textbook \"Linear Estimation\" by Sayed, Hassibi and Kailath.  That no such time-varying approach was used as a baseline was also disappointing, as this could likely have compensated for some of the errors introduced by nonlinear dynamics.\n\n- There has been a recent line of work on regret minimization based Kalman Filtering, which updates parameters/estimates online to compensate for the fact that \"effective noise\" is in fact rarely Gaussian or as modeled.  That no comparison to these baselines is presented is also disappointing.  These methods are further completely online, and require no labeled datasets for supervised learning.  Relevant papers to look at include:\n\n@article{goel2021regret,\n  title={Regret-optimal estimation and control},\n  author={Goel, Gautam and Hassibi, Babak},\n  journal={arXiv preprint arXiv:2106.12097},\n  year={2021}\n}\n\n@article{tsiamis2020online,\n  title={Online learning of the kalman filter with logarithmic regret},\n  author={Tsiamis, Anastasios and Pappas, George},\n  journal={arXiv preprint arXiv:2002.05141},\n  year={2020}\n}\n", "summary_of_the_paper": "This paper proposes using gradient-based optimization to tune the state and noise covariance parameters defining a Kalman Filter via supervised learning (i.e., assuming access to ground truth state measurements during training).  The need for this approach is motivated by the stringent assumptions under which optimality of the Kalman Filter is shown, and that these assumptions often fail in practice.  It is shown through several case-studies that the Optimized Kalman Filter (OKF) not only significantly outperforms a baseline KF implemented with estimated noise covariances, but also matches or outperforms Extended Kalman Filters and an LSTM-based \"neural KF\" introduced by the authors.", "summary_of_the_review": "While the paper highlights and addresses an important problem, and proposes a simple yet effective solution, I believe that without a comparison to *online Kalman Filtering* approaches that minimize regret, it is impossible to determine if this truly represents an improvement over the state of the art in terms of empirical performance.  From a theoretical perspective, I see little to no novelty in the paper's contributions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ll0b3tZfOP3", "reviewer": "Reviewer_NGZA", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of the paper is not clear to me.\nIt looks like that the paper tackles the problem of noise estimation of the Kalman filter in an alternative method. However, the paper is not written in a cohesive way which makes it very difficult to follow what it narrates. It is not clear how different parts of the paper are related to each other.\nThe paper contains many well established concepts that looks unnecessary to include in the paper. \nThe title of the paper does not explain what has been tackled in the paper.\n", "summary_of_the_paper": "The paper claims that optimization of the Kalman filter parameters are needed in cases where the filter assumptions are violated.", "summary_of_the_review": "The paper is not written well and does not have a flow. The rationale and objective of the paper is not clear. Therefore, I can not recommend it for publication. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ha02MUsb1OM", "reviewer": "Reviewer_Qzvj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "(+) The paper is well-organized and well-written.\n\n(+) Theoretical analyses of the proposed optimization method.\n\n(-) Noise estimation in KF models is a classical and open issue. The authors should carefully claim their contributions on this point.\n\n(-) The proposed method is a supervised learning method - ground truths are required - this is the major downside as compared to the regular KF methods.\n\n(-) Cholesky decomposition-based gradient descent is not novel for SPD matrices estimation.\n\n(-) Only benchmark datasets were used to demonstrate the superiority to the baseline KF. The data from practical applications are expected. Although a few samples of the filtering results over the real-world data were given in the appendices, no statistical comparisons were shown.\n\n(-) It is not clear on the explanation of the benchmark results - what is the scale of the errors obtained? They should be relative or percentage values, to better understand the improvements.\n\n(-) As ground truths are involved, it is interesting to see how the machine learning methods other than KF-related perform. It is reasonable to compare the proposed approach to the KF-related methods only. However, the ground truths are enforced, which are the most costly and most difficult to obtain in practice. From this perspective, it would be necessary to demonstrate the proposed KF approach performs comparably against these supervised machine learning methods other than KF-related.", "summary_of_the_paper": "This paper targets the design of a classical filtering method - the Kalman filter (KF). The linearity assumption is a strong limitation of KF models although a wide range of variants have been demonstrated for non-linear systems. Different from these studies, the authors focused on the estimation of the noise models in the KF(-class) models, in order to improve the accuracy and robustness of the KF estimates, through an optimization method. The proposed approach was assessed on a benchmark dataset, and the results demonstrated the superiority of the proposed method. Also theoretical analyses are provided in the appendices.", "summary_of_the_review": "Please refer to the weaknesses in the above section.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1KC7GyH6ocx", "reviewer": "Reviewer_Eeik", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is nice to read. I think the message that the paper is trying to convey is very clear, important and impactful. I appreciated the simplicity of the message, the style of the paper, and the effort in addressing its limitations and connection to related work. \n\nHowever, I am not convinced with the main message that the  optimization based procedure is better than noise estimation. In particular, I am not sure how do the authors evaluate the noise estimation for nonlinear setting, since the formulas given in paper are only for linear observation model. If, for nonlinear observation model y = h(x) + w , the noise covariance is estimated with Cov[y-h(x)] from data, then this is indeed the optimal estimator for the covariance matrix in mse. For a trajectory (x_k,y_k), the difference y_k - h(x_k) = w_k, where w_k are i.i.d, and empirical covariance of w_k is the best mse estimate for cov(w). So I would appreciate if the authors explain the noise estimation for nonlinear observation model and theoretically why is it bad. I read appendix E, but I did not understand the need for defining \\tilde{H}, why not use the full nonlinear observation model to estimate R.     \n\nMoreover, it is not clear if the proposed optimization procedure has a unique solution. For example, in (Formentin and Bittanti, 2014), it is shown that the KF estimate depends only on the ratio of noise covariances in scalar case. Therefore, the MSE optimization problem can only recover the ratio between noise covariances. So, it would be great if the paper have a clear and precise statement of the optimization problem it aims to solve, and analysis on why the minimizer is unique.    \n\nAlso, a main disadvantage of the proposed procedure is that the optimization problem is highly nonlinear and nonconvex, specially after Cholesky decompostion. The paper does not provide any guarantee for its convergence, unlike estimation which simply follows from law of large numbers. \n\nSome minor questions/issues:\n1- I could not find the result in (Humpherys et al., 2012) that the paper refers to. \n\n2- It will be good to add some classical adaptive filtering papers by Mehra and Carew and Bélanger.\n\n3- I don't think KF requires F and H to be time-invariant. \n\n4- I was confused by polar coordinates in 3d. Does it mean spherical? \n\n5- Does the proposed procedure have any advantage for linear Gaussian setting? \n\n\n   \n\n \n\n   ", "summary_of_the_paper": "The paper studies the problem of using Kalman filter for estimating the state of a dynamical system when the noise covariance matrices, for both state dynamics and observation, are unknown. The paper assumes access to trajectories of both state and observation. In this setting, a natural approach to solve the problem is to use the data to form an estimate for the covariance matrices. However, the paper argues that an optimization procedure to find noise covariance matrices to minimize the MSE is favorable and should become the \"new standard procedure for KF tuning\". With several numerical experiments, the paper illustrates that the optimization based KF tuning provides much better and robust result compared to standard KF based on estimation, and the comparisons made in the advanced neural network based estimation literature is not fair.\n\n\n\n\n ", "summary_of_the_review": "I recommend marginally below acceptance threshold. I think the paper is well-written, but it should be much more precise mathematically, explaining the estimation procedure for nonlinear setting, and address some fundamental questions about the optimization problem.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of estimating the trajectory of a linear dynamical system when the covariances for the process and observation noise are unknown. The standard solution is to estimate these covariances from data, and this paper instead suggests an optimization procedure. They show promising experimental results. However there are two shortcomings: In terms of theoretical guarantees, they can only show convergence to a local optimum. Moreover they assume they have access to the ground-truth hidden states. Although this is an assumption that has appeared in earlier works, it seems to limit the applicability.
Decision: Reject