How does one apply Kalman smoothing with irregular time steps?

Question

I would like to apply Kalman smoothing to a series of data sampled at irregular time points. There is a claim on Stack Exchange that "For irregular spaced time series it's easy to construct a Kalman filter", but I haven't been able to find any literature that specifically addresses this.

In my situation, I'd like to use a simple exponential covariance relationship to reflect the idea that the underlying continuous process is evolving as a linear dynamical system from which we irregularly receive samples.

So: is it simply OK to apply a Kalman filter with the "predict" step using a transition model and a process noise model whose "amplitude" depend on the amount of time that has elapsed since the last measurement?

Answer 1

Yes. In fact, this is how the Kalman Filter (KF) is also set up, at least implicitly. The assumptions in place when choosing the KF model, are that the movements and measurements compose a linear dynamical system. The transition matrix, $F_{t-1}$, (in the equation: $\hat{x}_{t|t-1} = F_tx_{t-1} + ...$, where $\hat{x}$ is the predicted state estimate) is in fact indexed by time, so irregular observations shouldn't be an issue.

For a more mathematically rigorous explanation of the KF, Max Welling has a really good tutorial that I highly recommend.

Answer 2

The process (model) noise in a Kalman filter is assumed to be zero-mean Gaussian white noise. Under this assumption, the process noise at time t is independent from the process noise at t + dt. (Now this certainly may not be a valid assumption for the system one is actually attempting to model, but notwithstanding that, this is the assumption made for a Kalman filter.)

Fans of noise will recognize the time integral of Guassian white noise as a Wiener process, or Brownian motion. There are some heavy-hitting (for me, but thankfully not for Einstein and Norbert Wiener) mathematical derivations involved that boil down to roughly the same conclusion: The covariance of a white Gaussian noise distribution scales with the square root of time.

To use this for our Kalman Filter prediction step, let's start with Wikipedia's notation for a discrete-time Kalman Filter:

Let $\textbf{w}_k$ be process noise at time $k$,assumed to be drawn from a white noise (zero mean, time-uncorrelated) multivatiate Gaussian distribution with covariance $\textbf{Q}_k$.

The state covariance $\textbf{P}$ is increased during the prediction step according to

$\textbf{P}_{k|k-1}$ is the a priori state covariance estimate at timestep $k$ given all observations up to $k-1$, $\textbf{F}_k$ is the model dynamics at timestep $k$, and $\textbf{P}_{k-1|k-1}$ is the a posteriori state covariance estimate at timestep $k-1$ given all observations up to timestep $k-1$.

Intuitively, the process noise covariance $\textbf{Q}$ depends on time. Over an infinitesimal time, the noise itself cannot change more than infinitesimally, and likewise neither can the process noise covariance. Implicitly (in discrete time KF notation), $\textbf{Q}_k$ represents the Wiener Process for an independent standard normal noise variable evaluated over the time of one timestep. But we can also evaluate the Wiener Process over an arbitrary time window. Let's express this by letting $\textbf{Q}(\Delta)$ represent the process noise covariance for an arbitrary time difference $\Delta$, or the shift in the Wiener process over time.

Now we run into a bit of a notation shift, because a "timestep" is a discrete unit of time whereas we prefer a continuous expression. To circumvent this, let $\Delta_k$ be the time difference between two consecutive timesteps, say $k$ and $k-1$. When $\Delta$ = $\Delta_k$, then $\textbf{Q}(\Delta)$ = $\textbf{Q}_k$

Let's move briefly into the notation adopted by Wiener Process:

The following expression holds for a Wiener Process $W$ (here evaluated at times $t_2$ and $t_1$ ), where $Z$ is an independent standard normal noise variable.

Rearranging, we obtain an expression for the change in a Wiener process over time:

$W_{t2} - W_{t1} = \sqrt{t_2 - t_1} \cdot Z$

Now, shifting for the last time back to Kalman filter notation, we note that $\textbf{Q}(\Delta)$ also represents the shift in a Wiener Process over time. We can thus write the expression for $\textbf{Q}(\Delta)$ as:

$\textbf{Q}(\Delta) = \sqrt{\Delta} \cdot Z$

Final Takeaways:

Intuitively, it makes sense that the integration of white process noise over time would not result in linear scaling because at each infinitesimal timestep the process noise is equally likely to be positive or negative. We would instead expect the scaling to approach linearity if the noise was highly time-correlated (i.e. if the process noise at time t is positive, the process noise at time t+dt is likely also positive).

From an implementation standpoint, this is all fairly straightforward. You'll likely have to do a fair amount of process and measurement noise fitting anyways, so to properly incorporate measurements at irregular time intervals, all you really need to do is to ensure that your process noise covariance is scaled by a factor of the square root of the difference in time between the last filter state and the current measurement time ($\Delta$), which should look something along the lines of:

$\textbf{P}_{k|k-1} = \textbf{F}_k\textbf{P}_{k-1|k-1}\textbf{F}_k^{T} + \textbf{Q}(\Delta_k)$.

or

$\textbf{P}_{k|k-1} = \textbf{F}_k\textbf{P}_{k-1|k-1}\textbf{F}_k^{T} + \sqrt{\Delta_k} \cdot Z$.

Perhaps obvious but I'll point it out just in case, more than likely your model dynamics $\textbf{F}$ are also affected by a non-uniform timestep (i.e. if you have any sort of velocity / acceleration components). For simplicity this is not addressed here.