A Survey of Code Optimization Methods for Kalman Filter Extensions <s> Introduction <s> In this paper, a general class of stochastic estimation and control problems is formulated from the Bayesian Decision-Theoretic viewpoint. A discussion as to how these problems can be solved step by step in principle and practice from this approach is presented. As a specific example, the closed form Wiener-Kalman solution for linear estimation in Gaussian noise is derived. The purpose of the paper is to show that the Bayesian approach provides; 1) a general unifying framework within which to pursue further researches in stochastic estimation and control problems, and 2) the necessary computations and difficulties that must be overcome for these problems. An example of a nonlinear, non-Gaussian estimation problem is also solved. <s> BIB001 </s> A Survey of Code Optimization Methods for Kalman Filter Extensions <s> Introduction <s> The Bayesian recursion relations which describe the behavior of the a posteriori probability density function of the state of a time-discrete stochastic system conditioned on available measurement data cannot generally be solved in closed-form when the system is either non-linear or nongaussian. In this paper a density approximation involving convex combinations of gaussian density functions is introduced and proposed as a meaningful way of circumventing the difficulties encountered in evaluating these relations and in using the resulting densities to determine specific estimation policies. It is seen that as the number of terms in the gaussian sum increases without bound, the approximation converges uniformly to any density function in a large class. Further, any finite sum is itself a valid density function unlike many other approximations that have been investigated. The problem of determining the a posteriori density and minimum variance estimates for linear systems with nongaussian noise is treated using the gaussian sum approximation. This problem is considered because it can be dealt with in a relatively straightforward manner using the approximation but still contains most of the difficulties that one encounters in considering non-linear systems since the a posteriori density is nongaussian. After discussing the general problem from the point-of-view of applying gaussian sums, a numerical example is presented in which the actual statistics of the a posteriori density are compared with the values predicted by the gaussian sum and by the Kalman filter approximations. <s> BIB002 </s> A Survey of Code Optimization Methods for Kalman Filter Extensions <s> Introduction <s> We develop and analyze real-time and accurate filters for nonlinear filtering problems based on the Gaussian distributions. We present the systematic formulation of Gaussian filters and develop efficient and accurate numerical integration of the optimal filter. We also discuss the mixed Gaussian filters in which the conditional probability density is approximated by the sum of Gaussian distributions. A new update rule of weights for Gaussian sum filters is proposed. Our numerical tests demonstrate that new filters significantly improve the extended Kalman filter with no additional cost, and the new Gaussian sum filter has a nearly optimal performance. <s> BIB003 </s> A Survey of Code Optimization Methods for Kalman Filter Extensions <s> Introduction <s> From the Publisher: ::: "Estimation with Applications to Tracking and Navigation treats the estimation of various quantities from inherently inaccurate remote observations. It explains state estimator design using a balanced combination of linear systems, probability, and statistics." "The authors provide a review of the necessary background mathematical techniques and offer an overview of the basic concepts in estimation. They then provide detailed treatments of all the major issues in estimation with a focus on applying these techniques to real systems." "Suitable for graduate engineering students and engineers working in remote sensors and tracking, Estimation with Applications to Tracking and Navigation provides expert coverage of this important area."--BOOK JACKET. <s> BIB004 </s> A Survey of Code Optimization Methods for Kalman Filter Extensions <s> Introduction <s> By Matthew James Keelingand Pejman RohaniPrinceton, NJ: Princeton University Press,2008.408 pp., Illustrated. $65.00 (hardcover).Mathematical modeling of infectious dis-eases has progressed dramatically over thepast 3 decades and continues to ﬂourishat the nexus of mathematics, epidemiol-ogy, and infectious diseases research. Nowrecognized as a valuable tool, mathemat-ical models are being integrated into thepublic health decision-making processmore than ever before. However, despiterapid advancements in this area, a formaltraining program for mathematical mod-eling is lacking, and there are very fewbooks suitable for a broad readership. Tosupport this bridging science, a commonlanguage that is understood in all con-tributing disciplines is required. <s> BIB005 </s> A Survey of Code Optimization Methods for Kalman Filter Extensions <s> Introduction <s> In this paper, we present a regularization method in the nonstationary inverse problem for diffuse optical tomography (DOT). The regularization is based on a choosing time evolution process such that in a stationary state it has a covariance function which corresponds to a process with similar smoothness properties as the first-order smoothness Tikhonov regularization. The proposed method is computationally more lightweight than the method where the regularization is augmented as a measurement. The method was tested in the case of the inverse problem of DOT. A solid phantom with optical properties similar to tissue was made, incorporating two moving parts that simulate two different physiological processes: a localized change in absorption and a surrounding rotating two-part shell which simulates slow oscillations in the tissue background physiology. A sequence of measurements of the phantom was made and the reconstruction of the image sequence was computed using this method. It allows the recovery of the full time series of images from relatively slow measurements with one source active at a time. In practice, this allows instruments with a larger dynamic range to be applied to the imaging of functional phenomena using DOT. <s> BIB006 </s> A Survey of Code Optimization Methods for Kalman Filter Extensions <s> Introduction <s> Low-complexity Bayesian filtering for nonlinear models is challenging. Approximative methods based on Gaussian mixtures (GM) and particle filters are able to capture multimodality, but suffer from high computational demand. In this paper, we provide an in-depth analysis of a generalized GM (GGM), which allows component weights to be negative, and requires significantly fewer components than the traditional GM for ranging models. Based on simulations and tests with real data from a network of UWB nodes, we show how the algorithm's accuracy depends on the uncertainty of the measurements. For nonlinear ranging the GGM filter outperforms the extended Kalman filter (EKF) in both positioning accuracy and consistency in environments with uncertain measurements, and requires only slightly higher computational effort when the number of measurement channels is small. In networks with highly reliable measurements, the GGM filter yields similar accuracy and better consistency than the EKF. <s> BIB007
Bayesian state estimation has a wide range of applications from positioning BIB007 and tracking BIB004 to brain imaging BIB006 and modeling spread of infectious diseases BIB005 . The number of state variables varies depending on the application e.g. in some positioning applications only 2 position variables are estimated, but in others the state may contain also variables for the locations of thousands of landmarks. In general, the Bayesian state estimate cannot be computed in closed form. Under certain conditions closed form solutions exist. For example, when measurement and state transition functions are linear and associated noises are Gaussian, the Bayesian state estimate can be computed in closed form by the Kalman Filter (KF) algorithm BIB001 . When the conditions are not met an approximation has to be used. Kalman Filter Extensions (KFEs) are based on approximate linear-Gaussian models. In the literature, there are several different types of KFEs, with different demands on computational resources. The computational complexity of the KFE increases when the number of estimated state variables or dimensionality of the measurement vector increases; in some KFEs even exponentially BIB003 . In many applications the computational resources are severely limited e.g. when doing tracking using wearable devices. In this survey, we study different methods to optimize the computation of the state estimation with KFEs by exploiting the structure of the state transition and measurement models. We assume that the reader is familiar with the basics of KFEs. The presented algorithms are such that the result is exact when applied to a situation where the KF produces the exact result. We give the algorithms in a general form so that they can be applied to as wide a range of problems as possible, but still in a form that they are easy to implement. Some of the surveyed algorithms in the original sources are given only for a certain KFE. The general notation used in this survey allows the optimizations to be implemented for different KFEs. In the literature, there is not a similar unified presentation of different optimization methods. In addition to surveying the algorithms in the literature, we give some generalizations of the algorithms and new ways of applying the optimizations with the KFEs. A drawback of KFEs is that the estimate is approximated as a Gaussian, which makes the estimate inaccurate when the true posterior is far from normal. Gaussian Mixture Filters (GMFs) (a.k.a. Gaussian sum filters) use a sum of normal densities to estimate the probability distributions and can approximate any probability density function BIB002 . Because GMFs use several KFEs the computational load is larger than with algorithms that use only one Gaussian. The optimizations in this survey can be applied also in the GMFs for state propagation and update of individual components. For implementations, we assume that a library for basic linear algebra is available. In many practical applications, the algorithms can be optimized further by taking the application specific structure of the matrices into account. Often the matrices are sparse, and the sparsity can be exploited for optimization either by hand or by implementing the algorithms with sparsity-optimized subroutines. These can be found, for example, in Sparse Basic Linear Algebra Subprograms 1 or in Matlab 2 . The computation time of algorithms can also be reduced by using parallel computing. The matrix operations can be effectively parallelized and the parallelization can be done in the linear algebra library that handles the matrix operations. Thus, we do not consider parallelization in this survey. The remainder of this survey is organized as follows. In the next section we present the common notations that are used throughout the paper. In Section 3 the background of KFEs is presented. Section 4 contains linearity based optimizations of the KFEs. Section 5 presents optimizations based on unobserved and static state variables. In Section 6 the solution of the set of linear equations containing the inverse of the innovation covariance is optimized. Section 7 gives example applications of the optimization methods. Section 8 concludes the article.