Estimation of unknown noise covariances in a Kalman filter is a problem of significant practical interest in a wide array of applications. This paper presents a single-pass stochastic gradient descent (SGD) algorithm for noise covariance estimation for use in adaptive Kalman filters applied to non-stationary systems where the noise covariances can occasionally jump up or down by an unknown magnitude. Unlike our previous batch method or our multi-pass decision-directed algorithm, the proposed streaming algorithm reads measurement data exactly once and has similar root mean square error (RMSE). The computational efficiency of the new algorithm stems from its one-pass nature, recursive fading memory estimation of the sample cross-correlations of the innovations, and the RMSprop accelerated SGD algorithm. The comparative evaluation of the proposed method on a number of test cases demonstrates its computational efficiency and accuracy.

Estimation of unknown noise covariances in a Kalman filter is a problem of significant practical interest in a wide array of applications. Although this problem has a long history, reliable algorithms for their estimation were scant, and necessary and sufficient conditions for identifiability of the covariances were in dispute until recently. Necessary and sufficient conditions for covariance estimation and a batch estimation algorithm. This paper presents stochastic gradient descent (SGD) algorithms for noise covariance estimation in adaptive Kalman filters that are an order of magnitude faster than the batch method for similar or better root mean square error (RMSE) and are applicable to non-stationary systems where the noise covariances can occasionally jump up or down by an unknown magnitude. The computational efficiency of the new algorithm stems from adaptive thresholds for convergence, recursive fading memory estimation of the sample cross-correlations of the innovations, and accelerated SGD algorithms. The comparative evaluation of the proposed method on a number of test cases demonstrates its computational efficiency and accuracy.

Identification of when and where moving areas intersect is an important problem in maritime operations and air traffic control. This problem can become particularly complicated when considering large numbers of objects, and when taking into account the curvature of the earth. In this paper, we present an approach to conflict identification as a series of stages where the earlier stages are fast, but may result in a false detection of a conflict. These early stages are used to reduce the number of potential conflict pairs for the later stages, which are slower, but more precise. The stages use R-trees, polygon intersection, linear projection and nonlinear programming. Our approach is generally applicable to objects moving in piece-wise straight lines on a 2D plane, and we present a specific case where the Mercator Projection is used to transform objects moving along rhumb lines on the earth into straight lines to fit in our approach. We present several examples to demonstrate our methods, as well as to quantify the empirical time complexity by using randomly generated areas.

The Kalman filter requires knowledge of the noise statistics; however, the noise covariances are generally unknown. Although this problem has a long history, reliable algorithms for their estimation are scant, and necessary and sufficient conditions for identifiability of the covariances are in dispute. We address both of these issues in this paper. We first present the necessary and sufficient condition for unknown noise covariance estimation; these conditions are related to the rank of a matrix involving the auto and cross-covariances of a weighted sum of innovations, where the weights are the coefficients of the the minimal polynomial of the closed-loop system transition matrix of a stable, but not necessarily optimal, Kalman filter. We present an optimization criterion and a novel six-step approach based on a successive approximation, coupled with a gradient algorithm with adaptive step sizes, to estimate the steady-state Kalman filter gain, the unknown noise covariance matrices, as well as the state prediction (and updated) error covariance matrix. Our approach enforces the structural assumptions on unknown noise covariances and ensures symmetry and positive definiteness of the estimated covariance matrices. We provide several approaches to estimate the unknown measurement noise covariance R via post-fit residuals, an approach not yet exploited in the literature. The validation of the proposed method on five different test cases from the literature demonstrates that the proposed method significantly outperforms previous state-of-the-art methods. It also offers a number of novel machine learning motivated approaches, such as sequential (one sample at a time) and mini-batch-based methods, to speed up the computations.