Links between Kalman Filtering and Data Assimilation with Generalized Least Squares ()

William Menke^{}

Lamont-Doherty Earth Observatory of Columbia University, Palisades, USA.

**DOI: **10.4236/am.2022.136036
PDF HTML XML
75
Downloads
352
Views
Citations

Lamont-Doherty Earth Observatory of Columbia University, Palisades, USA.

Kalman filtering (KF) is a popular form of data assimilation, especially in real-time applications. It combines observations with an equation that describes the dynamic evolution of a system to produce an estimate of its present-time state. Although KF does not use future information in producing an estimate of the state vector, later reanalysis of the archival data set can produce an improved estimate, in which all data, past, present and future, contribute. We examine the case in which the reanalysis is performed using generalized least squares (GLS), and establish the relationship between the real-time Kalman estimate and the GLS reanalysis. We show that the KF solution at a given time is equal to the GLS solution that one would obtain if data excluded future times. Furthermore, we show that the recursive procedure in KF is exactly equivalent to the solution of the GLS problem via Thomas’ algorithm for solving the block-tridiagonal matrix that arises in the reanalysis problem. This connection suggests that GLS reanalysis is better considered the final step of a single process, rather than a “different method” arbitrarily being applied, post factor. The connection also allows the concept of resolution, so important in other areas of inverse theory, to be applied to KF formulations. In an exemplary thermal diffusion problem, model resolution is found to be somewhat localized in both time and space, but with an extremely rough averaging kernel.

Keywords

Kalman Filter, Generalized Least Squares, Bayesian Inference, Data Assimilation, Real-Time, Resolution

Share and Cite:

Menke, W. (2022) Links between Kalman Filtering and Data Assimilation with Generalized Least Squares. *Applied Mathematics*, **13**, 566-584. doi: 10.4236/am.2022.136036.

1. Introduction

In this paper, we compare two data assimilation methods that are routinely applied to monitor time-dependent of linear systems, one based on Generalized Least Squares (GLS) [1] and the other on Kalman Filtering (KF) [2] [3]. We are motivated by our anecdotal observation that, while both are widely used tools that do broadly similar things, GSL and KF tend to be used by different communities who often think of their method as the “best”. Our goal is to enumerate and study the similarities and differences between the GLS and KF. Especially, we wish to determine whether or not the same prior information is used in each. Establishing a link between KF and GLS provides a clear pathway for applying GLS concepts, and especially resolution analysis [4] [5], to KF, and also a pathway for extending GLS analysis to the real-time scenarios for which KF is already well-suited.

A synopsis of variables used in this paper is provided in Table 1. At any time, ${t}_{i}$, $1\le i\le K$, a linear system is described by a state vector (model parameter vector), ${m}^{\left(i\right)}\in {\mathbb{R}}^{M}$. This state vector evolves away from the initial condition

${m}^{\left(1\right)}={m}_{A}^{\left(1\right)}$ (1)

according to the dynamical equation:

${m}^{\left(i\right)}=D{m}^{\left(i-1\right)}+{s}^{\left(i-1\right)}$ (2)

Here, $D$ is the dynamics matrix and $s\in {\mathbb{R}}^{M}$ is the source vector. Neither

Table 1. List of variables.

the initial conditions nor the source is known exactly, but rather have uncertainty described by their respective covariance matrices, ${C}_{A1}$ and ${C}_{s}$.

This formulation well approximates the behavior of systems described by linear partial differential equations that are first order in time. For example, let ${m}_{n}^{\left(i\right)}=m\left({x}_{n},{t}_{i}\right)$ be temperature at time, ${t}_{i}=i\Delta t$, and position, ${x}_{n}=n\Delta x$, where $\Delta t$ and $\Delta x$ are small increments, and suppose that $m\left(x,t\right)$ satisfies the thermal diffusion equation, $\partial m/\partial t=c{\partial}^{2}m/\partial {x}^{2}+q$ (with zero boundary conditions). This partial differential equation can be approximated by:

$\frac{{m}^{\left(i\right)}-{m}^{\left(i-1\right)}}{\Delta t}=\frac{c}{{\left(\Delta x\right)}^{2}}{\Delta}_{2}{m}^{\left(i-1\right)}+{q}^{\left(i-1\right)}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{or}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{m}^{\left(i\right)}=D{m}^{\left(i-1\right)}+{s}^{\left(i-1\right)}$

$\text{with}\text{\hspace{0.17em}}\text{\hspace{0.05em}}D=\left(\frac{c\Delta t}{{\left(\Delta x\right)}^{2}}{\Delta}_{2}+I\right){m}^{\left(i-1\right)}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{s}^{\left(i-1\right)}=\Delta t{q}^{\left(i-1\right)}$ (3)

which has the form of dynamical Equation (2). Here, the choices:

${\Delta}_{2}\equiv \left[\begin{array}{cccccc}1& & & & & \\ 1& -2& 1& & & \\ & 1& -2& 1& & \\ & & & & \ddots & \\ & & & 1& -2& 1\\ & & & & & 1\end{array}\right]\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{q}^{\left(i-1\right)}=\left[\begin{array}{c}0\\ {q}_{2}^{\left(i-1\right)}\\ \vdots \\ {q}_{M-1}^{\left(i-1\right)}\\ 0\end{array}\right]$ (4)

encode both the differential equation and the boundary conditions. The matrix, $D$, is sparse in this example, as well as in many other cases in which it approximates a differential operator.

The data equation expresses the relationship between the state vector and the observables:

${G}^{\left(i\right)}{m}^{\left(i\right)}={d}^{\left(i\right)}$ (5)

Here,
${d}^{\left(i\right)}\in {\mathbb{R}}^{N}$ is the data vector, determined to covariance,
${C}_{d}$, and
${G}^{\left(i\right)}$ is the data kernel. In the simplest case, the observations may be of selected elements of the state vector, itself, in which case, each row of
$G$ is zero, except for a single element, say in column, *k*, which is unity. Here,
$k\left(i,n\right)$ is a function that associates
${d}_{n}^{\left(i\right)}$ with
${m}_{k}^{\left(i\right)}$. Other more complicated relationships are possible. For instance, in tomography, the data is a line integral through
$m\left(x,y,t\right)$ (with *y* another spatial dimension). The data kernel,
$G$, is sparse in these two cases. In other cases, it may not be sparse.

The data assimilation problem is to estimate the set of state vectors, $\left\{{m}^{\left(i\right)}:1<i\le K\right\}$, using the dynamical equation, the data equation and the initial condition. One possible approach is based on Generalized Least Squares (GLS); another upon Kalman Filtering (KF). In this paper, we demonstrate that these two apparently very different methods are, in fact, exactly equivalent. In order to simplify notation, we concatenate the state vectors for times into an overall vector, $m=\left[{m}^{\left(i\right)},\cdots ,{m}^{\left(K\right)}\right]$, and data vectors into an overall vector, $d=\left[{d}^{\left(2\right)},\cdots ,{d}^{\left(N\right)}\right]$. By assumption, no observations are made at time, $i=1$.

2. Generalized Least Squares Applied to the Data Assimilation Problem

Generalized Least Squares (GLS) [1] [6] [7] [8] is a technique used to estimate $m$ when two types of information are available: prior information and data. By prior information, we mean expectations about the behavior of $m$ that are based on past experience or general physical considerations. The dynamical equation and initial condition discussed in the previous section are examples of prior information. By data we mean direct observations, as typified by the data equation discussed in the previous section.

Prior information can be represented by the linear equation, $Hm=h$ (with $h\in {\mathbb{R}}^{L}$ and where the equation is accurate to covariance, ${C}_{h}$ ) and observations can be represented by the linear equation, $Gm=d$ (with covariance ${C}_{o}$ ). The Bayesian principle leads to the optimal solution, which we denote the Generalize Least Squares (GLS) solution, ${m}_{G}$ [1] [6] [7] [8]. It minimizes a combination of the weighted ${L}_{2}$ error in prior information and the weighted ${L}_{2}$ error in the data (where the weighting depends upon the covariances).

Several equivalent forms of the GLS solution, ${m}_{G}$, and its posterior variance, ${C}_{m}$, are common in the literature. We enumerate a few of the more commonly-used forms here:

Form 1 [8] groups the prior information and data equations into a single equation, $Fm=h$ :

${m}_{G}={\left[{F}^{\text{T}}F\right]}^{-1}{F}^{\text{T}}f\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{with}\text{\hspace{0.17em}}\text{\hspace{0.05em}}F\equiv \left[\begin{array}{c}{C}_{h}^{-1/2}H\\ {C}_{o}^{-1/2}G\end{array}\right]\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}f\equiv \left[\begin{array}{c}{C}_{h}^{-1/2}h\\ {C}_{o}^{-1/2}d\end{array}\right]$

${C}_{m}={\left[{F}^{\text{T}}F\right]}^{-1}$ (6)

Note that the factors of ${C}_{h}^{-1/2}$ amd ${C}_{o}^{-1/2}$ are weights proportional to “certainty”.

Form 2 [1] introduces generalized inverses, ${G}^{-g}$ and ${H}^{-g}$ :

${m}_{G}={G}^{-g}d+{H}^{-g}h$

$\text{with}\text{\hspace{0.17em}}\text{\hspace{0.05em}}{G}^{-g}\equiv {A}^{-1}{G}^{\text{T}}{C}_{o}^{-1}\text{\hspace{0.17em}}\text{\hspace{0.05em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.05em}}{H}^{-g}\equiv {A}^{-1}{H}^{\text{T}}{C}_{h}^{-1}\text{\hspace{0.05em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.05em}}A\equiv {G}^{\text{T}}{C}_{o}^{-1}G+{H}^{\text{T}}{C}_{h}^{-1}H$

${C}_{m}={A}^{-1}$ (7)

Here, ${m}_{G}$ is the estimated solution and ${C}_{m}$ is its posterior covariance.

Form 3 [7] organizes the solution in terms of the prior state vector, ${m}_{A}$ ; that is, the state vector implied by the prior information, acting alone:

${m}_{G}={G}^{-g}d+{P}_{G}{m}_{A}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{with}\text{\hspace{0.17em}}{P}_{G}\equiv \left(I-{G}^{-g}G\right)$

$\text{and}\text{\hspace{0.17em}}\text{with}\text{\hspace{0.17em}}{m}_{A}\equiv \{\begin{array}{ll}{H}^{-1}h\hfill & \exists {H}^{-1}\hfill \\ {\left[{H}^{\text{T}}{C}_{h}^{-1}H\right]}^{-1}{H}^{\text{T}}{C}_{h}^{-1}h\hfill & \nexists {H}^{-1}\hfill \end{array}\text{\hspace{0.17em}}\text{\hspace{0.05em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.05em}}{C}_{A}={\left[{H}^{\text{T}}{C}_{h}^{-1}H\right]}^{-1}$

${C}_{m}={P}_{G}{C}_{A}$ (8)

The matrix, ${P}_{G}$, plays the role of a projection matrix. See Appendix A.1 for a deviation of the covariance equation.

Form 4 [1] introduces the deviation, $\Delta m$, of the solution from the prior state vector, and the corresponding deviation, $\Delta d$, of the data from that predicted by the prior state vector:

$\Delta m={G}^{-g}\Delta d\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\Delta m\equiv {m}_{G}-{m}_{A}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\Delta d\equiv d-G{m}_{A}$ (9)

Finally, Form 5 [6] [9] uses as alternate form of the generalized inverse:

$\Delta m={{G}^{\prime}}^{-g}\Delta d\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{with}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{{G}^{\prime}}^{-g}\equiv {C}_{A}{G}^{\text{T}}{A}^{\ast}{}^{-1}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{A}^{\ast}\equiv \left[{C}_{o}+G{C}_{A}{G}^{\text{T}}\right]$ (10)

The equality of the two forms was proven by [6] using a matrix identity that we denote TV82-A (Appendix A.2). Because $A$ is $M\times M$ and ${A}^{\ast}$ is $N\times N$, the first form is most useful when $M<N$ ; the second when $M>N$. However, a decision to use one or the other must also take in consideration the sparsity of the various matrix products.

Form 4 is derived from Form 3 by subtracting $A{m}_{A}$ from both sides of the Gram equation,

$A\left({m}_{G}-{m}_{A}\right)=a-A{m}_{A}$

$\left[{G}^{\text{T}}{C}_{o}^{-1}G+{H}^{\text{T}}{C}_{h}^{-1}H\right]\left({m}_{G}-{m}_{A}\right)={G}^{\text{T}}{C}_{o}^{-1}\left(d-G{m}_{A}\right)+{H}^{\text{T}}{C}_{h}^{-1}\left(h-H{m}_{A}\right)$ (11)

and then by requiring that the second term on the right-hand side vanish, which leads to:

$A\Delta m={G}^{\text{T}}{C}_{o}^{-1}\Delta d\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{with}\text{\hspace{0.17em}}\text{\hspace{0.05em}}\Delta d=d-G{m}_{A}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{m}_{A}={\left[{H}^{\text{T}}{C}_{h}^{-1}H\right]}^{-1}{H}^{\text{T}}{C}_{h}^{-1}h$ (12)

That is, ${m}_{A}$ is due to the prior information acting along. The deviatoric manipulation is completely general; alternately the first term could have been made to vanish, in which leads to:

$A\Delta m={H}^{\text{T}}{C}_{h}^{-1}\Delta h\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{with}\text{\hspace{0.17em}}\text{\hspace{0.05em}}\Delta h=h-H{m}_{G}\text{\hspace{0.17em}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{m}_{G}={\left[{G}^{\text{T}}{C}_{o}^{-1}G\right]}^{-1}{G}^{\text{T}}{C}_{o}^{-1}d$ (13)

Here, ${m}_{G}$ is due to the data acting alone. Note that deviatoric manipulations of this type never change the form of the matrix, $A$. We will apply this principle later in the paper.

In the subsequent analysis, we will focus on the Gram equations:

$Am={G}^{\text{T}}{C}_{o}^{-1}d\equiv a$ (14)

The initial condition and the dynamical equation can be into a single prior information equation of the form, $Hm=h$ :

$\left[\begin{array}{ccccc}I& & & & \\ -D& I& & & \\ & -D& I& & \\ & & & \ddots & \\ & & & -D& I\end{array}\right]\left[\begin{array}{c}{m}^{\left(1\right)}\\ {m}^{\left(2\right)}\\ {m}^{\left(3\right)}\\ \vdots \\ {m}^{\left(K\right)}\end{array}\right]=\left[\begin{array}{c}{m}_{A}^{\left(1\right)}\\ {s}^{\left(1\right)}\\ {s}^{\left(2\right)}\\ \vdots \\ {s}^{\left(K-1\right)}\end{array}\right]\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{withcovariance}\text{\hspace{0.17em}}\text{\hspace{0.05em}}{C}_{h}$ (15)

Here, ${C}_{h}\equiv \text{diag}\left({C}_{A1},{C}_{s},{C}_{s},\cdots ,{C}_{s}\right)$. Several quantities derived from $H$, and which we will use later, are:

${H}^{\text{T}}=\left[\begin{array}{ccccc}I& -{D}^{\text{T}}& & & \\ & I& -{D}^{\text{T}}& & \\ & & I& -{D}^{\text{T}}& \\ & & & \ddots & \\ & & & I& -{D}^{\text{T}}\\ & & & & I\end{array}\right]\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{H}^{-1}=\left[\begin{array}{ccccc}I& & & & \\ D& I& & & \\ {D}^{2}& D& I& & \\ {D}^{3}& {D}^{2}& D& I& \\ & & & & \ddots \end{array}\right]$

${H}^{\text{T}}{C}_{h}^{-1}H=\left[\begin{array}{ccccc}\left[{C}_{A1}^{-1}+{D}^{\text{T}}{C}_{s}^{-1}D\right]& -{D}^{\text{T}}{C}_{s}^{-1}& 0& & \\ -{C}_{s}^{-1}D& \left[{C}_{s}^{-1}+{D}^{\text{T}}{C}_{s}^{-1}D\right]& -{D}^{\text{T}}{C}_{s}^{-1}& & \\ & -{C}_{s}^{-1}D& \left[{C}_{s}^{-1}+{D}^{\text{T}}{C}_{s}^{-1}D\right]& & \\ & & & \ddots & -{D}^{\text{T}}{C}_{s}^{-1}\\ & & & -{D}^{\text{T}}{C}_{s}^{-1}& {C}_{s}^{-1}\end{array}\right]$

${H}^{\text{T}}{C}_{h}^{-1}h=\left[\begin{array}{c}{C}_{A1}^{-1}{m}_{A}^{\left(1\right)}-{D}^{\text{T}}{C}_{s}^{-1}{s}^{\left(1\right)}\\ {C}_{s}^{-1}{s}^{\left(1\right)}-{D}^{\text{T}}{C}_{s}^{-1}{s}^{\left(2\right)}\\ \vdots \\ {C}_{s}^{-1}{s}^{\left(N-1\right)}-{D}^{\text{T}}{C}_{s}^{-1}{s}^{\left(N\right)}\\ {C}_{s}^{-1}{s}^{\left(N\right)}\end{array}\right]$ (16)

The existence of ${H}^{-1}$ implies that ${m}_{A}$ can be uniquely specified. The data equation expresses the relationship between the state vector and the observables, and presuming that no data are available for time, $i=1$, has the form:

$\left[\begin{array}{ccccc}0& {G}^{\left(2\right)}& & & \\ & & & \ddots & \\ & & & & {G}^{\left(N\right)}\end{array}\right]\left[\begin{array}{c}{m}^{\left(1\right)}\\ {m}^{\left(2\right)}\\ \vdots \\ {m}^{\left(M\right)}\end{array}\right]=\left[\begin{array}{c}{d}^{\left(2\right)}\\ {d}^{\left(3\right)}\\ \vdots \\ {d}^{\left(N\right)}\end{array}\right]$ (17)

This equation is taken to have an accuracy described by the summary covariance matrix,*
${C}_{o}\equiv \text{diag}\left({C}_{d},{C}_{d},{C}_{d},\cdots ,{C}_{d}\right)$ *. We note that:

$\begin{array}{l}{G}^{\text{T}}{C}_{d}^{-1}G=\left[\begin{array}{cccc}0& & & \\ & {G}^{\left(2\right)\text{T}}{C}_{d}^{-1}{G}^{\left(2\right)\text{T}}& & \\ & & \ddots & \\ & & & {G}^{\left(K\right)\text{T}}{C}_{d}^{-1}{G}^{\left(K\right)\text{T}}\end{array}\right]\\ \text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{G}^{\text{T}}{C}_{d}^{-1}d=\left[\begin{array}{c}0\\ {G}^{\left(2\right)\text{T}}{C}_{d}^{-1}{d}^{\left(2\right)}\\ {G}^{\left(3\right)\text{T}}{C}_{d}^{-1}{d}^{\left(3\right)}\\ \vdots \\ {G}^{\left(K\right)\text{T}}{C}_{d}^{-1}{d}^{\left(N\right)}\end{array}\right]\end{array}$ (18)

The matrix, $A$, in the Gram equation is symmetric and block-triagonal:

$\left[\begin{array}{ccccc}{A}_{1}& {B}^{\text{T}}& & & \\ B& {A}_{2}& {B}^{\text{T}}& & \\ & & & & \\ & & & \ddots & {B}^{\text{T}}\\ & & & B& {A}_{N}\end{array}\right]\left[\begin{array}{c}{m}^{\left(1\right)}\\ {m}^{\left(2\right)}\\ {m}^{\left(3\right)}\\ \vdots \\ {m}^{\left(K\right)}\end{array}\right]=\left[\begin{array}{c}{a}_{1}\\ {a}_{2}\\ {a}_{3}\\ \vdots \\ {a}_{K}\end{array}\right]$ (19)

with elements:

${A}_{i}=\{\begin{array}{ll}\left[{D}^{\text{T}}{C}_{s}^{-1}D+{C}_{A1}^{-1}\right]\hfill & \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left(i=1\right)\hfill \\ \left[{D}^{\text{T}}{C}_{s}^{-1}D+{C}_{s}^{-1}+{G}^{\left(i\right)}{C}_{d}^{-1}{G}^{\left(i\right)\text{T}}\right]\hfill & \left(1<i<K\right)\hfill \\ {C}_{s}^{-1}+{G}^{\left(K\right)}{C}_{d}^{-1}{G}^{\left(K\right)\text{T}}\hfill & \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left(i=K\right)\hfill \end{array}$

$B=-{C}_{s}^{-1}D$ (20)

The vector, $a$, on the right-hand side of the Gram equation, is:

${a}_{i}=\{\begin{array}{ll}\left[-{D}^{\text{T}}{C}_{s}^{-1}{s}^{\left(1\right)}+{C}_{A1}^{-1}{m}_{A}^{\left(1\right)}\right]\hfill & \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left(i=1\right)\hfill \\ \left[-{D}^{\text{T}}{C}_{s}^{-1}{s}^{\left(i\right)}+{C}_{s}^{-1}{s}^{\left(i-1\right)}+{G}^{\left(i\right)\text{T}}{C}_{d}^{-1}{d}^{\left(i\right)}\right]\hfill & \left(1<i<K\right)\hfill \\ {C}_{s}^{-1}{s}^{\left(i-1\right)}+{G}^{\left(i\right)\text{T}}{C}_{d}^{-1}{d}^{\left(i\right)}\hfill & \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left(i=K\right)\hfill \end{array}$ (21)

Here, we define ${s}^{\left(K\right)}$ to be zero.

3. Recursive Solution Using the Thomas Method

Insight into the behavior of the GLS solution can be gained by solving the Gram equation iteratively [10]. We the Thomas method [11] [12] (see Appendix A.3), though other methods are viable alternatives. It consists of a forward-in-time pass through the system that recursively calculates two quantities, ${\stackrel{^}{A}}_{i}$ and ${\stackrel{^}{a}}_{i}$ :

${\stackrel{^}{A}}_{i}^{-1}\equiv \{\begin{array}{ll}{A}_{1}^{-1}\hfill & \left(i=1\right)\hfill \\ {\left[{A}_{i}-B{\stackrel{^}{A}}_{i-1}^{-1}{B}^{\text{T}}\right]}^{-1}\hfill & \left(i>1\right)\hfill \end{array}$

${\stackrel{^}{a}}_{i}\equiv \{\begin{array}{ll}{a}_{1}\hfill & \left(i=1\right)\hfill \\ \left[{a}_{i}-B{\stackrel{^}{A}}_{i-1}^{-1}{\stackrel{^}{a}}_{i-1}\right]\hfill & \left(i>1\right)\hfill \end{array}$ (22)

After the forward recursion, the system is block-upper-bidiagonal with row *i* having elements
${\stackrel{^}{A}}_{i}$ and
${B}^{\text{T}}$ (except for the last row, which lacks the
${B}^{\text{T}}$ ) and the modified right-hand side is
${\stackrel{^}{a}}_{i}$. The solution,
${m}_{G}^{\left(i\right)}$, is achieved through a backward recursion:

${m}_{G}^{\left(i\right)}=\{\begin{array}{ll}{\stackrel{^}{A}}_{K}^{-1}{\stackrel{^}{a}}_{K}\hfill & \left(i=K\right)\hfill \\ {\stackrel{^}{A}}_{i}^{-1}\left[{\stackrel{^}{a}}_{i}-{B}^{\text{T}}{m}^{\left(i+1\right)}\right]\hfill & \left(i<K\right)\hfill \end{array}$ (23)

It is evident that information is propagated both forward and backward in time during the solution process. Furthermore, computation time grows no faster than the number of steps, *K*, in the recursion.

The Thomas method has a disadvantage in the common case where the covariances matrices,
${C}_{A1},{C}_{s}$ and
${C}_{d}$ are diagonal and when
$D$ and
${G}^{\left(i\right)}$ are sparse, because although
$F$ is then also sparse, the matrices,
${\stackrel{^}{A}}_{i}^{-1}$, are in general not sparse, so the effort needed to compute them scales with
${M}^{3}$. Other direct methods share this limitation, too. Consequently, the overall calculation scales with*
$K{M}^{3}$.* An iterative method [10], such conjugate gradient method, applied to the Gram equation,
${F}^{\text{T}}Fm={F}^{\text{T}}h$, is usually a better choice. This method requires that the quantity,
$u=\left({F}^{\text{T}}F\right)v$, be calculated for an arbitrary vector,
$v$, and this quantity can be very efficiently calculated as
$u={F}^{\text{T}}\left(Fv\right)$ [13]. In cases in which the dynamical equation approximates a partial differential equation, the number of non-zero elements in the matrix,
$F$, scale with
$KM$. The conjugate gradient algorithm requires no more than
$KM$ iterations (and often much fewer), each requiring
$KM$ multiplications. Thus, the overall solution time scales with
${K}^{2}{M}^{2}$. Consequently, the conjugate gradient method has a speed advantage when
$M>K$.

4. Present-Time Solution

Suppose that the analysis focuses on the “present-time”, *i*, in the sense that only the solution,
${m}_{P}^{\left(i\right)}$, determined using data up to and including time, *i*, is of interest. One can assemble a sequence of present-time solutions during the forward recursion, using the fact that the *i*th solution can always be considered to be the final one. No backwards recursion is needed to compute the solution for the final time. However, the forms of the “final”
${\stackrel{^}{A}}_{i}$ and
${\stackrel{^}{a}}_{i}$ differ from that of the previous
$A$ s in the recursion, so a separate computation is needed:

${m}_{P}^{\left(i\right)}={{\stackrel{^}{A}}^{\prime}}_{i}^{-1}{{\stackrel{^}{a}}^{\prime}}_{i}$

${{\stackrel{^}{A}}^{\prime}}_{i}={\stackrel{^}{A}}_{i}-{D}^{\text{T}}{C}_{s}^{-1}D={C}_{si}^{-1}+{G}^{\left(i\right)}{C}_{d}^{-1}{G}^{\left(i\right)\text{T}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{{\stackrel{^}{a}}^{\prime}}_{i}={\stackrel{^}{a}}_{i}+{D}^{\text{T}}{C}_{s}^{-1}{s}^{\left(i\right)}$ (24)

Consequently, in order to create a sequence of present-time solution, the two linear systems must be solved at each step in the forward recursion. The present-time solution is the same as the reference solution, ${m}_{D}^{\left(i\right)}$, defined in the previous section.

Kalman Filtering

Kalman Filtering (KF) is a solution method with an algorithm that, like the Thomas present-time solution, is forward-in-time, only [2] [3]. It consists of four steps, the final three which are iterated.

Step 1 assigns the $i=1$ solution, ${m}_{K}^{\left(1\right)}$, and its covariance, ${C}_{m}^{\left(1\right)}$ :

${m}_{K}^{\left(1\right)}={m}_{A}^{\left(1\right)}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{C}_{m}^{\left(1\right)}={C}_{A1}$ (25)

Step 2 propagates the solution and its covariance forward in time using the dynamical equation, and considers it to be prior information.

${m}_{A}^{\left(i\right)}=\left(D{m}_{K}^{\left(i-1\right)}+{s}^{\left(i-1\right)}\right)\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{C}_{A}^{\left(i\right)}=D{C}_{m}^{\left(i-1\right)}{D}^{\text{T}}+{C}_{s}$ (26)

Step 3 uses GLS to combine the prior information, ${m}_{A}^{\left(i\right)}$, with covariance ${C}_{A}^{\left(i\right)}$, and data, ${d}^{\left(i\right)}$, with covariance ${C}_{d}$, into a solution, ${m}_{K}^{\left(i\right)}$, with covariance, ${C}_{m}$. Any of the equivalent forms of the GLS solutions described in Section 2 can be used in this step.

Step 4, increments *i* and returns to Step 2, creating a recursion.

Most often, the GLS solution and its variance are written as:

${m}_{K}^{\left(i\right)}={m}_{A}^{\left(i\right)}+{G}_{i}^{-g}\Delta {d}^{\left(i\right)}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{with}\text{\hspace{0.17em}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}\Delta {d}^{\left(i\right)}={d}^{\left(i\right)}-{G}^{\left(i\right)}{m}_{A}^{(\; i\; )}$

$\text{with}\text{\hspace{0.17em}}\text{\hspace{0.05em}}{G}_{i}^{-g}={C}_{A}^{\left(i\right)}{G}^{\left(i\right)\text{T}}{\left[{C}_{d}^{\left(i\right)}+{G}^{\left(i\right)}{C}_{A}^{\left(i\right)}{G}^{\left(i\right)\text{T}}\right]}^{-1}\text{\hspace{0.17em}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{C}_{A}^{\left(i\right)}=D{C}_{m}^{\left(i-1\right)}{D}^{\text{T}}+{C}_{s}$

$\text{and}\text{\hspace{0.17em}}\text{\hspace{0.05em}}{C}_{m}^{\left(i\right)}=\left[I-{G}_{i}^{-g}{G}^{\left(i\right)}\right]{C}_{A}^{\left(i\right)}={P}_{G}^{\left(i\right)}{C}_{A}^{\left(i\right)}\text{\hspace{0.17em}}\text{\hspace{0.05em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.05em}}{P}_{G}^{\left(i\right)}\equiv \left[I-{G}_{i}^{-g}{G}^{\left(i\right)}\right]$ (27)

However, any of the equivalent forms described above can substitute, such as:

${m}_{K}^{\left(i\right)}={\stackrel{\u02dc}{A}}_{i}^{-1}{\stackrel{\u02dc}{a}}_{i}$

${C}_{A}^{\left(i\right)}=D{C}_{m}^{\left(i-1\right)}{D}^{\text{T}}+{C}_{s}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\stackrel{\u02dc}{A}}_{i}^{-1}={\left[{G}^{\left(i\right)\text{T}}{C}_{d}^{-1}{G}^{\left(i\right)}+{\left[{C}_{A}^{\left(i\right)}\right]}^{-1}\right]}^{-1}={C}_{m}^{(\; i\; )}$

${\stackrel{\u02dc}{a}}_{i}={G}^{\left(i\right)\text{T}}{C}_{d}^{-1}d+{\left[{C}_{A}^{\left(i\right)}\right]}^{-1}D{m}_{K}^{\left(i-1\right)}+{\left[{C}_{A}^{\left(i\right)}\right]}^{-1}{s}^{\left(i-1\right)}$ (28)

5. Kalman Filtering Is Not “Filtering” in the Strict Sense

A standard Infinite Impulse Response (IIR) filter has the form $v\ast m=u\ast z$, where $z$ is the “input” timeseries, $m$ is the “output” timeseries, $u$ and $v$ are filters (with ${v}_{1}=1$ ) and $\ast $ signifies convolution [14]. Key to this formulation is that the filter coefficients are constants; that is, they are not a function of time.

If the generalized inverse in KF was time-independent, so that ${G}_{i}^{-g}={G}^{-g}$, then KF could be put into form of an IIR filter:

$\left[\begin{array}{c}\left[I\right]\\ \left[{G}^{-g}GD-I\right]\end{array}\right]\ast \left[\begin{array}{c}\vdots \\ {m}^{\left(i-1\right)}\\ {m}^{\left(i\right)}\\ \vdots \end{array}\right]=\left[\begin{array}{cc}{G}^{-g}& -{G}^{-g}G\end{array}\right]\ast \left[\begin{array}{c}\vdots \\ \left[\begin{array}{c}{d}^{\left(i-1\right)}\\ {s}^{\left(i-2\right)}\end{array}\right]\\ \left[\begin{array}{c}{d}^{\left(i\right)}\\ {s}^{\left(i-1\right)}\end{array}\right]\\ \vdots \end{array}\right]$ (29)

because the convolution reproduces the KF solution:

${m}^{\left(i\right)}={m}^{\left(i-1\right)}+{G}^{-g}\left({d}^{\left(i\right)}-G\left(D{m}^{\left(i-1\right)}+{s}^{\left(i-1\right)}\right)\right)$ (30)

So, from this point of view, the KF has a
$v$ of length 2 (each element of which is a matrix), and a
$u$ of length 1 (each element of which is a row vector of two matrices). However, this formulation does not really correspond to a standard IIR filter, because the filter coefficients, which depend upon the generalized inverse,
${G}_{i}^{-g}$, depend upon time, *i*. Hence, the word “filter”, though generally indicative of the KF process, oversimplifies the actual operation being performed. KF is not filtering in the strict sense.

6. The Present-Time Thomas and Kalman Filtering Solutions Are Equal

We will now demonstrate that the present-time Thomas solution, ${m}_{P}^{\left(i\right)}$, and the Kalman filtering solution, ${m}_{K}^{\left(i\right)}$, are equal. We will make use of an identity, abbreviated TV82-B, that is due to [6], which shows that for invertible symmetric matrices ${C}_{1}$ and ${C}_{2}$ and arbitrary matrix, $M$ :

${C}_{2}-{C}_{2}{M}^{\text{T}}{\left[M{C}_{2}{M}^{\text{T}}+{C}_{1}\right]}^{-1}M{C}_{2}={\left[{M}^{\text{T}}{C}_{1}^{-1}M+{C}_{2}^{-1}\right]}^{-1}$ (31)

Thus, for instance, when ${C}_{1}^{-1}={C}_{A}^{\left(i\right)}$, ${C}_{2}^{-1}={C}_{s}$ and $M={D}^{\text{T}}$ :

${\left[{C}_{A}^{\left(i\right)}\right]}^{-1}={\left[D{C}_{m}^{\left(i-1\right)}{D}^{\text{T}}+{C}_{s}\right]}^{-1}={C}_{s}^{-1}-{C}_{s}^{-1}D{\left[{D}^{\text{T}}{C}_{s}^{-1}D+{\left[{C}_{m}^{\left(i-1\right)}\right]}^{-1}\right]}^{-1}{D}^{\text{T}}{C}_{s}^{-1}$ (32)

The PT and KF recursions both start with ${m}_{K}^{\left(1\right)}={m}_{PT}^{\left(1\right)}={m}_{A}$ and ${C}_{KA}^{\left(1\right)}={C}_{PTA}^{\left(1\right)}={C}_{A}$. The $\left(i=2\right)$ case in irregular, and must be examine separately. The KF solution is:

${m}_{K}^{\left(2\right)}={\stackrel{\u02dc}{A}}_{2}^{-1}{\stackrel{\u02dc}{a}}_{2}$

$\text{with}\text{\hspace{0.17em}}\text{\hspace{0.05em}}{\stackrel{\u02dc}{A}}_{2}={G}^{\left(2\right)\text{T}}{C}_{d}^{-1}{G}^{\left(2\right)}+{\left[{C}_{A}^{\left(2\right)}\right]}^{-1}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{with}\text{\hspace{0.05em}}\text{\hspace{0.17em}}{C}_{A}^{\left(2\right)}=D{C}_{A1}{D}^{\text{T}}+{C}_{s}$

$\text{and}\text{\hspace{0.17em}}\text{\hspace{0.05em}}{\stackrel{\u02dc}{a}}_{2}={G}^{\left(2\right)\text{T}}{C}_{d}^{-1}{d}^{\left(2\right)}+{\left[{C}_{A}^{\left(2\right)}\right]}^{-1}D{m}_{K}^{\left(1\right)}+{\left[{C}_{A}^{\left(2\right)}\right]}^{-1}{s}^{\left(1\right)}$ (33)

This can be compared with the present-time Thomas solution:

${m}_{P}^{\left(2\right)}={{\stackrel{^}{A}}^{\prime}}_{2}^{-1}{{\stackrel{^}{a}}^{\prime}}_{2}$

$\begin{array}{l}\text{with}\text{\hspace{0.17em}}\text{\hspace{0.05em}}{{\stackrel{^}{A}}^{\prime}}_{2}={G}^{\left(2\right)}{C}_{d}^{-1}{G}^{\left(2\right)\text{T}}+{C}_{s}^{-1}-{C}_{s}^{-1}D{\left[{D}^{\text{T}}{C}_{s}^{-1}D+{C}_{A1}^{-1}\right]}^{-1}{D}^{\text{T}}{C}_{s}^{-1}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}={G}^{\left(2\right)}{C}_{d}^{-1}{G}^{\left(2\right)\text{T}}+{\left[D{C}_{A1}{D}^{\text{T}}+{C}_{s}\right]}^{-1}\end{array}$

${{\stackrel{^}{a}}^{\prime}}_{2}={G}^{\left(2\right)\text{T}}{C}_{d}^{-1}{d}^{\left(2\right)}+{C}_{s}^{-1}{s}^{\left(1\right)}-{C}_{s}^{-1}D{\stackrel{^}{A}}_{1}^{-1}{D}^{\text{T}}{C}_{s}^{-1}{s}^{\left(1\right)}+{C}_{s}^{-1}D{\stackrel{^}{A}}_{1}^{-1}{C}_{s}^{-1}D{C}_{A1}^{-1}{m}_{A}$ (34)

Note that we used TV82-B to simplify the expression for ${\stackrel{^}{A}}_{2}$. By inspection, ${{\stackrel{^}{A}}^{\prime}}_{2}={\stackrel{\u02dc}{A}}_{2}$. Thus, the two solutions are equal if ${{\stackrel{^}{a}}^{\prime}}_{2}={\stackrel{\u02dc}{a}}_{2}$. The terms involving ${d}^{\left(2\right)}$ match. The terms involving ${s}^{\left(1\right)}$ would match if it could be shown that:

${C}_{s}^{-1}-{C}_{s}^{-1}D{\left[{D}^{\text{T}}{C}_{s}^{-1}D+{C}_{A1}^{-1}\right]}^{-1}{D}^{\text{T}}{C}_{s}^{-1}\stackrel{?}{=}{\left[D{C}_{A1}{D}^{\text{T}}+{C}_{s}\right]}^{-1}$ (35)

But this equation is true by TV82-B. The terms ${m}_{A}$ also match, because of the matrix identity

${\left[D{C}_{A1}{D}^{\text{T}}+{C}_{s}\right]}^{-1}D={C}_{s}^{-1}D{\left[{D}^{\text{T}}{C}_{s}^{-1}D+{C}_{A1}^{-1}\right]}^{-1}D{C}_{A1}^{-1}$ (36)

derived in Appendix A.4. Consequently, the solutions, ${m}_{K}^{\left(2\right)}={m}_{P}^{\left(2\right)}$, and their posterior covariances, ${C}_{Km}^{\left(2\right)}={{\stackrel{^}{A}}^{\prime}}_{2}^{-1}={C}_{Pm}^{\left(2\right)}={\stackrel{\u02dc}{A}}_{2}^{-1}$ are equal. Applying ${C}_{Km}^{\left(i\right)}={\stackrel{\u02dc}{A}}_{i}^{-1}$ to the KF recursion, and TV82-B and ${\stackrel{^}{A}}_{i}={{\stackrel{^}{A}}^{\prime}}_{i}+{D}^{\text{T}}{C}_{s}^{-1}{D}^{\text{T}}$ to present-time Thomas recursion, leads to:

${\stackrel{\u02dc}{A}}_{i+1}={G}^{\left(i+1\right)\text{T}}{C}_{d}^{-1}{G}^{\left(i+1\right)}+{\left[D{\stackrel{\u02dc}{A}}_{i}^{-1}{D}^{\text{T}}+{C}_{s}\right]}^{-1}$

$\begin{array}{c}{{\stackrel{^}{A}}^{\prime}}_{i+1}={G}^{\left(i+1\right)}{C}_{d}^{-1}{G}^{\left(i+1\right)\text{T}}+{C}_{s}^{-1}-{C}_{s}^{-1}D{\left[{D}^{\text{T}}{C}_{s}^{-1}D+{{\stackrel{^}{A}}^{\prime}}_{i}\right]}^{-1}{D}^{\text{T}}{C}_{s}^{-1}\\ ={G}^{\left(i+1\right)}{C}_{d}^{-1}{G}^{\left(i+1\right)\text{T}}+{\left[D{{\stackrel{^}{A}}^{\prime}}_{i}^{-1}{D}^{\text{T}}+{C}_{s}\right]}^{-1}\end{array}$ (37)

Thus, ${\stackrel{\u02dc}{A}}_{i+1}={{\stackrel{^}{A}}^{\prime}}_{i+1}$ as long as ${\stackrel{\u02dc}{A}}_{i}^{-1}={{\stackrel{^}{A}}^{\prime}}_{i}^{-1}$. Because the latter is true for $i=2$, so the formula can be successively applied to show ${\stackrel{\u02dc}{A}}_{i+1}={{\stackrel{^}{A}}^{\prime}}_{i+1}$ for all $i>2$. Similarly, the procedure that demonstrated the equality of ${\stackrel{^}{a}}_{2}$ and ${\stackrel{\u02dc}{a}}_{2}$ can be extended to

${\stackrel{\u02dc}{a}}_{i+1}={G}^{\left(i+1\right)\text{T}}{C}_{d}^{-1}{d}^{\left(i+1\right)}+{\left[D{\stackrel{\u02dc}{A}}_{i}^{-1}{D}^{\text{T}}+{C}_{s}\right]}^{-1}{s}^{\left(i\right)}+{\left[D{\stackrel{\u02dc}{A}}_{i}^{-1}{D}^{\text{T}}+{C}_{s}\right]}^{-1}D{m}_{K}^{(\; i\; )}$

and

$\begin{array}{c}{\stackrel{^}{a}}_{i+1}={C}_{s}^{-1}{s}^{\left(i\right)}+{G}^{\left(i+1\right)\text{T}}{C}_{d}^{-1}{d}^{\left(i+1\right)}+{C}_{s}^{-1}D{\stackrel{^}{A}}_{i}^{-1}\left[{{\stackrel{^}{a}}^{\prime}}_{i}-{D}^{\text{T}}{C}_{s}^{-1}{s}^{\left(i\right)}\right]\\ ={G}^{\left(i+1\right)\text{T}}{C}_{d}^{-1}{d}^{\left(i+1\right)}+\left[{C}_{s}^{-1}-{C}_{s}^{-1}D{\stackrel{^}{A}}_{i}^{-1}{D}^{\text{T}}{C}_{s}^{-1}\right]{s}^{\left(i\right)}+{C}_{s}^{-1}D{\stackrel{^}{A}}_{i}^{-1}{{\stackrel{^}{a}}^{\prime}}_{i}\\ ={G}^{\left(i+1\right)\text{T}}{C}_{d}^{-1}{d}^{\left(i+1\right)}+{\left[{C}_{s}+D{{\stackrel{^}{A}}^{\prime}}_{i}^{-1}{D}^{\text{T}}\right]}^{-1}{s}^{\left(i\right)}+{C}_{s}^{-1}D{\stackrel{^}{A}}_{i}^{-1}{{\stackrel{^}{A}}^{\prime}}_{i}{m}_{P}^{\left(i\right)}\end{array}$ (38)

Here we have used TV82-B and ${m}_{P}^{\left(i\right)}={\stackrel{^}{A}}_{i}^{-1}{{\stackrel{^}{a}}^{\prime}}_{i}$. The terms ending in ${d}^{\left(i+1\right)}$ match. The terms ending in ${s}^{\left(i\right)}$ also match, since it has been established previously that ${\stackrel{\u02dc}{A}}_{i}^{-1}={{\stackrel{^}{A}}^{\prime}}_{i}^{-1}$. In order for ${\stackrel{\u02dc}{a}}_{i+1}$ to equal ${\stackrel{^}{a}}_{i+1}$, we must have ${m}_{P}^{\left(i\right)}={m}_{K}^{\left(i\right)}$ and:

${\left[D{\stackrel{\u02dc}{A}}_{i}^{-1}{D}^{\text{T}}+{C}_{s}\right]}^{-1}D\stackrel{?}{=}{C}_{s}^{-1}D\left[{{\stackrel{^}{A}}^{\prime}}_{i}^{-1}+{D}^{\text{T}}{C}_{s}^{-1}D\right]{{\stackrel{^}{A}}^{\prime}}_{i}$ (39)

This equation has the same form as identity (36), where the equality has been demonstrated. Starting with $i=2$, we have ${m}_{P}^{\left(2\right)}={m}_{K}^{\left(2\right)}$ and ${{\stackrel{^}{A}}^{\prime}}_{2}={\stackrel{\u02dc}{A}}_{2}$, which implies ${{\stackrel{^}{A}}^{\prime}}_{3}={\stackrel{\u02dc}{A}}_{3}$ and ${\stackrel{^}{a}}_{3}={\stackrel{\u02dc}{a}}_{3}$, which implies ${m}_{P}^{\left(3\right)}={m}_{K}^{\left(3\right)}$. This process can be iterated indefinitely, establishing that the present-time Thomas and Kalman solutions, and their posterior variance, are equal.

7. Comparison between the Present-Time Solution and GLS

The present-time solutions at time, *j*, depends on information available for times,
$\left(i\le j\right)$ but not upon information that subsequently becomes available (that is, for times
$\left(i>j\right)$. This limitation is necessary in a real-time scenario. However, the lack of future data leads to a solution that is poorer estimate of the true solution, than a GLS solution in which the state vectors at all time are globally adjusted to best-fit all the prior information and data.

An outlier that occurs at, or immediately before, the present moment can cause large error in the present-time solution. The full GLS solution is less affected because measurements in the near future may compensate (Figure 1).

Having established links between KF and GLS, we are now able to apply several useful inverse theory concepts and especially resolution [4] [5] [7]. In a GLS problem, model resolution refers to the ability of the data assimilation process to reconstruct deviations of the true model from the one predicted by the prior information, alone [1]. Data resolution refers to its ability to reconstruct deviations of the data from the one predicted by the prior information [9]. Model resolution is quantified by a $\left(KM\right)\times \left(KM\right)$ matrix, $R={G}^{-g}G$ and data resolution by a $\left(KN\right)\times \left(KN\right)$ matrix, $N=G{G}^{-g}$, that satisfy.

$\left(m-{m}_{A}\right)=R\left({m}^{true}-{m}_{A}\right)\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left(d-G{m}_{A}\right)=N\left({m}^{true}-G{m}_{A}\right)$ (40)

Figure 1. Hypothetical data assimilation scenario, with $K=4$, $M=N=1$, $\text{D}=1$, $\text{s}=0.25$. The initial condition (red box) satisfies ${\text{m}}_{A}^{\left(0\right)}=0$. The dynamical equation requires that the slope (dotted red lines) be about 1/4. The data, ${d}^{\left(i\right)}$, are noisy versions of state ${m}^{\left(i\right)}$, which is expected to linearly increase with time with slope, s. When the “present-time” is $i=3$, the present-time solution (grey), ${m}_{P}^{\left(3\right)}$, is pulled down by the noisy datum, ${d}^{\left(i\right)}$, leading to a poor fit to the dynamics at that time. The GLS solution, ${m}_{G}^{\left(3\right)}$, is less affected by the outlier, because the datum at time, $i=4$, better defines the linear trend, leading to a solution at $i=3$ that better matched the dynamics.

Resolution is perfect when $R=N=I$. When $R\ne I$, an element of the reconstructed state vector is a weighted average of all elements of the true state vector. When $N\ne I$, an element of the reconstructed data vector is a weighted average of all elements of the true data vector. The resolution matrices quantify resolution in both time and space. As we will show in the example, below, the model resolution (or data resolution) can be temporally poor, even when it is spatially good.

Another important quantity is the full $\left(KM\right)\times \left(KM\right)$ posterior covariance matrix, ${C}_{m}={\left[{F}^{\text{T}}F\right]}^{-1}$. In addition to correlations between elements of the state vector at a given time, it contains the correlations between elements of the state vectors at different times. These coefficients are needed for computing confidence intervals of quantities that depend of the state vectors at two or more times. Although $R$, $N$ and ${C}_{m}$ are large matrices, methods are available for efficiently computing selected elements of them using the conjugate gradient method [1].

Finally, there may be instances in which the covariance,
${C}_{s}\left(p\right)$, may be known only up to some scalar parameter,
$p\in \mathbb{R}$. For example, the choice
${\left[{C}_{s}\left(p\right)\right]}_{ij}={\gamma}^{2}\mathrm{exp}\left\{-\frac{1}{2}{p}^{-2}{\left({x}_{i}-{x}_{j}\right)}^{2}\right\}$ expresses decorrelation over a scale length, *p*. An initially poor guess of the parameter, *p*, can be “tuned” using partial derivatives based on the Bayesian principle [15] and the gradient descent method [16].

8. Example

We consider a data assimilation problem based on the heat diffusion Equation (3), with $\Delta t=\Delta x=1$ and ${c}_{0}=0.4$. The state vector, ${m}^{\left(i\right)}$, represents temperature at position, $x$, and is of length $M=31$. The source is Gaussian function in space and impulsive function in time, plus additive noise:

${s}_{j}^{\left(i\right)}=\mathrm{exp}\left[-\frac{1}{2}{s}_{x}^{-2}{\left({x}_{j}-\stackrel{\xaf}{x}\right)}^{2}\right]{\delta}_{i1}+{n}_{s}^{\left(j\right)}$ (41)

with scale length, ${s}_{x}=5$, and peak position, $\stackrel{\xaf}{x}=\frac{1}{2}M\Delta x$. Here, ${n}_{s}^{\left(j\right)}$ is a Normally-distributed random variable with zero mean and variance, ${\sigma}_{s}^{2}=0.05$. The initial condition is:

${\left[{\text{m}}_{A}^{\left(0\right)}\right]}_{i}={m}_{0}+{n}_{A}^{\left(j\right)}$ (42)

where ${m}_{0}=0.1$ and ${n}_{A}^{\left(j\right)}$ is a Normally-distributed random variable with zero mean and variance, ${\sigma}_{d}^{2}=0.07$. The dynamical Equation (2) is iterated for $K=61$ time steps, to provide the “true” state vector. As expected, the solution has a Gaussian shape with a width that increases, and an amplitude that decreased, with time (Figure 2(A)). The data are a total of $N=10$ temperature measurement at each time, $i\ge 2$, made at randomly-selected positions (without duplications) and perturbed with Normally-distributed random noise with zero mean and variance, ${\sigma}_{d}^{2}=0.10$.

GLS solutions were computed by both the full Thomas algorithm (Figure 2(B)) and by solving the $\left[{F}^{\text{T}}F\right]m={F}^{\text{T}}f$ system by the conjugate gradient method (not

Figure 2. Comparison of solutions. (A) True solution. (B) Difference between the Generalized least squares solution and the true solution. (C) Difference between the present-time Thomas solution and the true solution. (C) Difference between the Kalman solution and the true solution. Note that color scale for differences is expanded with respect to the one for the true model.

shown). They were found to be identical to machine precision. Present-time solutions were computed for both the present-time Thomas (Figure 2(C)) and KF algorithms (Figure 2(D)). They were also found to be identical to machine precision.

In general, both the GLS and present-time solutions fit the data well. However, the present-time solution matches the true model more poorly than does the GLS solution (Figure 3). In this numerical experiment, the present-time solution is about 10% poorer than the GLS solution, quantified with the root mean squared deviation from the true solution. However, the percentage, while always positive, varies considerably when the underlying parameters are changed.

Both the Thomas and Kalman versions of the present-time algorithm are well suited for providing ongoing diagnostic information, such as posterior covariance and root mean squared data fitting error (Figure 4), which can provide quality control in real time applications.

Figure 3. Histogram of ratios of the root mean squared error between the present-time estimate, ${m}_{P}^{\left(i\right)}$, $i=1,\cdots ,K$, and the true state and the root mean squared error between GLS estimate, ${m}_{G}^{\left(i\right)}$, $i=1,\cdots ,K$, and the true state, for 1000 realizations of the exemplary data assimilation problem.

Figure 4. Kalman Filtering solution of the exemplary data assimilation problem. (A) the data,
${d}^{\left(i\right)}$,
$i=1,\cdots ,N$. (B) The estimated state
${m}_{K}^{\left(i\right)}$,
$i=1,\cdots ,K$. (C) The root mean square data prediction as a function of time, *i*. (D) The posterior variance as a function of time, *i*.

The model resolution matrix,
$R$, (Figure 5(A)) for this exemplary problem has a poorly-populated central diagonal, meaning that some elements of the state vector,
${m}_{j}^{\left(i\right)}$, are well-resolved from their spatial neighbors,
${m}_{j\pm 1}^{\left(i\right)}$ while others are very poorly resolved. The matrix large elements along other diagonals, corresponding to, offset from the main diagonal by *M* rows, indicating that some elements are not well resolved from their temporal neighbors,
${m}_{j}^{\left(i\pm 1\right)}$. The temporal width of the resolving kernel is about ±4, and the shape is very irregular, indicating very uneven averaging is taking place (Figure 6). The data resolution matrix,
$N$, (Figure 5(A)) has a well-populated central diagonal, meaning that mosts elements of the predicted data vector,
${d}_{j}^{pre\left(i\right)}$, are well-resolved from their spatial neighbors,
${d}_{j\pm 1}^{pre\left(i\right)}$. Like
$R$, it also has elements along other diagonals, corresponding to, offset from the main diagonal by *M* rows, indicating that some elements are not well resolved from their temporal neighbors,
${d}_{j}^{pre\left(i\pm 1\right)}$.

Figure 5. Central portion of the resolution matrices for the exemplary data assimilation problem. (A) The model resolution matrix, $R$. (B) The data resolution matrix, $N$. The portion shown corresponds time slices $20\le i\le 23$.

Figure 6. Rows of the model resolution matrix, $R$ (colors), rearranged into an $\left(x,t\right)$ grid, for three target points (circles) (A) $x=15,t=12$ ; (B) $x=15,t=25$ ; (C) $x=15,t=38$. The high intensities are localized near the target points (good), but have a rough pattern (bad).

9. Conclusion

In this paper, we examine a data processing scenario in which real-time data assimilation is performed using Kalman Filtering, and then reanalysis is performed using generalized least squares (GLS). In this problem, spatial characteristics of the system are described by a state vector (mode parameter vector), and its temporal characteristics by the evolution of the state-vector with time. We explore the relationship between the real-time Kalman Filter estimate and the GLS reanalysis estimate of the state vector. We show that the KF solution at a given time is equal to the GLS solution that one would obtain if it excluded data for future times. Furthermore, we show that the recursive procedure in KF is exactly equivalent to the solution of the GLS problem via Thomas’ algorithm for solving the block-tridiagonal matrix that arises in the reanalysis problem. This connection indicates that GLS reanalysis is better considered the final step of a single process, rather than a “different method” arbitrarily being applied, post factor. Now that this connection between KF and GLS has seen identified, the familiar GLS concepts of model and data resolution can be applied to KF. We provide an exemplary problem, based on thermal diffusion. In addition to showcasing our result, the example demonstrates that the state vector and vector of predicted data can be poorly-resolved in time, even when they are well resolved in space.

Acknowledgements

The author thanks the students in his 2022 Geophysical Inverse Theory course at Columbia University (New York, USA), and especially George Lu, for helpful discussion.

Appendix

A.1) Proof that ${C}_{m}=\left[I-{G}^{-g}G\right]{C}_{A}\equiv {P}_{G}{C}_{A}$. This derivation is well known [6], but is presented here for completeness and to point out potential pitfalls should it be applied incorrectly. Because $d$ and ${m}_{A}$ are independent of one another, ${m}_{G}={G}^{-g}\left(d-G{m}_{A}\right)+{m}_{A}={G}^{-g}d+\left(\text{I}-{G}^{-g}G\right){m}_{A}$, the normal rules of error propagation apply. The posterior covariance, ${C}_{m}$, is:

$\begin{array}{c}{C}_{m}={G}^{-g}{C}_{d}{G}^{-g\text{T}}+\left(I-{G}^{-g}G\right){C}_{A}\left(I-{G}^{\text{T}}{G}^{-g\text{T}}\right)\\ ={C}_{A}+{G}^{-g}{C}_{d}{G}^{-g\text{T}}+{G}^{-g}G{C}_{A}{G}^{\text{T}}{G}^{-g\text{T}}-{C}_{A}{G}^{\text{T}}{G}^{-g\text{T}}-{G}^{-g}G{C}_{A}\\ ={C}_{A}+{G}^{-g}\left[G{C}_{A}{G}^{\text{T}}+{C}_{d}\right]{G}^{-g\text{T}}-{C}_{A}{G}^{\text{T}}{G}^{-g\text{T}}-{G}^{-g}G{C}_{A}\\ ={C}_{A}+{C}_{A}{G}^{\text{T}}{A}^{-1}A{A}^{-1}G{C}_{A}-{C}_{A}{G}^{\text{T}}{A}^{-1}G{C}_{A}-{C}_{A}{G}^{\text{T}}{A}^{-1}G{C}_{A}\\ ={C}_{A}+{C}_{A}{G}^{\text{T}}{A}^{-1}G{C}_{A}-{C}_{A}{G}^{\text{T}}{A}^{-1}G{C}_{A}-{C}_{A}{G}^{\text{T}}{A}^{-1}G{C}_{A}\\ ={C}_{A}-{C}_{A}{G}^{\text{T}}{A}^{-1}G{C}_{A}={C}_{A}-{G}^{-g}G{C}_{A}=\left[I-{G}^{-g}G\right]{C}_{A}\equiv {P}_{G}{C}_{A}\end{array}$ (A.1)

Here, we have used the fact that ${G}^{-g}={C}_{A}{G}^{\text{T}}{A}^{-1}$, with $A=\left[G{C}_{A}{G}^{\text{T}}+{C}_{d}\right]$. Although ${P}_{G}$, has the form of a projection operator, it is a function of ${C}_{A}$, and has deceptive properties. Consider the case in which ${C}_{A}=\epsilon S$, where $S$ is an invertible symmetric matrix. In the limit of the parameter, $\epsilon $, becoming indefinitely large, ${C}_{m}$ does not also become indefinitely large, but rather tends to ${\left[{G}^{\text{T}}{C}_{d}^{-1}G\right]}^{-1}$, which is the posterior variance that arises from the data, only. The zero limit tends to zero; that is, when ${m}_{A}$ is known very accurately, so is ${m}_{G}$.

A.2) Derivation of the TV82-A and TV82-B identities, following [6]. Consider invertible symmetric matrices, ${C}_{1}$ and ${C}_{2}$, and arbitrary matrix, $M$. The expression ${M}^{\text{T}}+{M}^{\text{T}}{C}_{1}^{-1}M{C}_{2}{M}^{\text{T}}$ can alternately be factored:

${M}^{\text{T}}{C}_{1}^{-1}\left[{C}_{1}+M{C}_{2}{M}^{\text{T}}\right]=\left[{C}_{2}^{-1}+{M}^{\text{T}}{C}_{1}^{-1}M\right]{C}_{2}{M}^{\text{T}}$ (A.2)

Multiplying by the inverses yields identity TV82-A:

${C}_{2}{M}^{\text{T}}{\left[{C}_{1}+M{C}_{2}{M}^{\text{T}}\right]}^{-1}={\left[{C}_{2}^{-1}+{M}^{\text{T}}{C}_{1}^{-1}M\right]}^{-1}{M}^{\text{T}}{C}_{1}^{-1}$ (A.3)

Now consider the expression ${C}_{2}-{C}_{2}{M}^{\text{T}}{\left[{C}_{1}+M{C}_{2}{M}^{\text{T}}\right]}^{-1}M{C}_{2}$, which by the above identity equals ${C}_{2}-{\left[{C}_{2}+{M}^{\text{T}}{C}_{1}^{-1}M\right]}^{-1}{M}^{\text{T}}{C}_{1}^{-1}M{C}_{2}$. Factoring out the term in brackets

${\left[{C}_{2}^{-1}+{M}^{\text{T}}{C}_{1}^{-1}M\right]}^{-1}\left[\left[{C}_{2}^{-1}+{M}^{\text{T}}{C}_{1}^{-1}M\right]{C}_{2}-{M}^{\text{T}}{C}_{1}^{-1}M{C}_{2}\right]$ (A.4)

cancelling terms yields identity TV82-B:

${C}_{2}-{C}_{2}{M}^{\text{T}}{\left[{C}_{1}+M{C}_{2}{M}^{\text{T}}\right]}^{-1}M{C}_{2}={\left[{C}_{2}^{-1}+{M}^{\text{T}}{C}_{1}^{-1}M\right]}^{-1}$ (A.5)

A.3) The Thomas algorithm [10] for a symmetric block-diagonal matrix is well-known; we reproduce it here for completeness. The th row of the matrix has elements $B$, ${A}_{i}$, ${B}^{\text{T}}$ and the right-hand size is ${a}_{i}$. Consider the step in the upper-triangularization process when rows $\left(i-1\right)$ and above have been triangularized, but rows $\left(i-1\right)$ and below have not:

${\stackrel{^}{A}}_{i-1}{m}^{\left(i-1\right)}+{B}^{\text{T}}{m}^{\left(i\right)}={\stackrel{^}{a}}_{i-1}$

$B{m}^{\left(i-1\right)}+{A}_{i}{m}^{\left(i\right)}+{B}^{\text{T}}{m}^{\left(i+1\right)}={a}_{i}$ (A.6)

The second row is modified by multiply the top row by $-B{\stackrel{^}{A}}_{i-1}^{-1}$ and adding the result to the second, which eliminates the first term, yielding:

$\left[{A}_{i}-B{\stackrel{^}{A}}_{i-1}^{-1}{B}^{\text{T}}\right]{m}^{\left(i\right)}+{B}^{\text{T}}{m}^{\left(i+1\right)}={a}_{i}-B{\stackrel{^}{A}}_{i-1}^{-1}{\stackrel{^}{a}}_{i-1}$ (A.7)

Note that the new row has two terms, and that the coefficient of the second is always ${B}^{\text{T}}$, which is the same pattern as the first row. Thus, the bottom row becomes a new top row, and the recursion is

${\stackrel{^}{A}}_{1}^{-1}={A}_{1}^{-1}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{followed}\text{\hspace{0.17em}}\text{by}\text{\hspace{0.17em}}{\stackrel{^}{A}}_{i}^{-1}={\left[{A}_{i}-B{\stackrel{^}{A}}_{i-1}^{-1}{B}^{\text{T}}\right]}^{-1}$

${\stackrel{^}{a}}_{1}={a}_{1}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{followed}\text{\hspace{0.17em}}\text{by}\text{\hspace{0.17em}}\text{\hspace{0.05em}}{\stackrel{^}{a}}_{i}={a}_{i}-B{\stackrel{^}{A}}_{i-1}^{-1}{\stackrel{^}{a}}_{i-1}$ (A.8)

After the recursion, the matrix upper-bidiagonal with diagonals, ${\stackrel{^}{A}}_{i}$ and ${B}^{\text{T}}$ and the right-hand side is ${\stackrel{^}{a}}_{i}$. It is back-solved as:

${m}^{\left(K\right)}={\stackrel{^}{A}}_{K}^{-1}{\stackrel{^}{a}}_{K}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{followed}\text{\hspace{0.17em}}\text{by}\text{\hspace{0.17em}}\text{\hspace{0.05em}}{m}^{\left(i\right)}={\stackrel{^}{A}}_{i}^{-1}\left[{\stackrel{^}{a}}_{i}-{B}^{\text{T}}{m}^{\left(i+1\right)}\right]$ (A.9)

A.4) Verification of the identity in (36):

${\left[D{C}_{A1}{D}^{\text{T}}+{C}_{s}\right]}^{-1}D\stackrel{?}{=}{C}_{s}^{-1}D{\left[{D}^{\text{T}}{C}_{s}^{-1}D+{C}_{A1}^{-1}\right]}^{-1}D{C}_{A1}^{-1}$

${\left[D{C}_{A1}{D}^{\text{T}}+{C}_{s}\right]}^{-1}D{C}_{A1}\stackrel{?}{=}{C}_{s}^{-1}D{\left[{D}^{\text{T}}{C}_{s}^{-1}D+{C}_{A1}^{-1}\right]}^{-1}$

$D{C}_{A1}\left[{D}^{\text{T}}{C}_{s}^{-1}D+{C}_{A1}^{-1}\right]\stackrel{?}{=}\left[D{C}_{A1}{D}^{\text{T}}+{C}_{s}\right]{C}_{s}^{-1}D$

$\left[D{C}_{A1}{D}^{T}{C}_{s}^{-1}D+D\right]=\left[D{C}_{A1}{D}^{T}{C}_{s}^{-1}D+D\right]$ (A.10)

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

[1] |
Menke, W. (2014) Review of the Generalized Least Squares Method. Surveys in Geophysics, 36, 1-25. https://doi.org/10.1007/s10712-014-9303-1 |

[2] | Stratonovich, R.L. (1959) Optimum Nonlinear Systems Which Bring about a Separation of a Signal with Constant Parameters from Noise. Radiofizika, 2, 892-901. |

[3] | Zarchan, P. and Musoff, H. (2000) Fundamentals of Kalman Filtering: A Practical Approach. American Institute of Aeronautics and Astronautics, Reston. |

[4] |
Backus, G. and Gilbert, F. (1968) The Resolving Power of Gross Earth Data. Geophysical Journal International, 16, 169-205. https://doi.org/10.1111/j.1365-246X.1968.tb00216.x |

[5] |
Wiggins, R.A. (1972) The General Linear Inverse Problem: Implications of Surface Waves and free Oscillations for Earth Structure. Reviews of Geophysics, 10, 251-285. https://doi.org/10.1029/RG010i001p00251 |

[6] | Tarantola, A. and Valette, B. (1982) Inverse Problems = Quest for Information. Journal of Geophysics, 50, 159-170. |

[7] | Menke, W. (2018) Geophysical Data Analysis: Discrete Inverse Theory. 4th Edition (Textbook), Elsevier, Amsterdam, 350. |

[8] |
Menke, W. and Menke, J. (2016) Environmental Data Analysis with MATLAB. 2nd Edition, Academic Press (Elsevier), Cambridge, MA, 342 p. https://doi.org/10.1016/C2015-0-01993-1 |

[9] |
Menke, W. and Creel, R. (2021) Gaussian Process Regression Reviewed in the Context of Inverse Theory. Surveys in Geophysics, 42, 473-503. https://doi.org/10.1007/s10712-021-09640-w |

[10] |
Dax, A. (2020) The Equivalence between Orthogonal Iterations and Alternating Least Squares. Advances in Linear Algebra & Matrix Theory, 10, 7-21. https://doi.org/10.4236/alamt.2020.102002 |

[11] | Thomas, L.H. (1949) Elliptic Problems in Linear Difference Equations over a Network. Watson Scientific Computing Laboratory Report, Columbia University, New York, 71. |

[12] | Press, W.H., Teukolsky, S.A., Vetterling, W.T. and Flannery, B.P. (2007) Numerical Recipes: The Art of Scientific Computing. 3rd Edition, Cambridge University Press, New York. |

[13] |
Menke, W. (2005) Case Studies of Seismic Tomography and Earthquake Location in a Regional Context. In: Levander, A. and Nolet, G., Eds., Seismic Earth: Array Analysis of Broadband Seismograms, Vol. 157, American Geophysical Union, Washington DC, 7-36. https://doi.org/10.1029/157GM02 |

[14] |
Schlichthärle, D. (2000) Digital Filters: Basics and Design. Springer, Berlin, 361 p. https://doi.org/10.1007/978-3-662-04170-3 |

[15] |
Menke, W. (2021) Tuning of Prior Covariance in Generalized Least Squares. Applied Mathematics, 12, 157-170. https://doi.org/10.4236/am.2021.123011 |

[16] |
Snyman, J.A. and Wilke, D.N. (2018) Practical Mathematical Optimization: Basic Optimization Theory and Gradient-Based Algorithms. Springer Optimization and Its Applications, Vol. 133, 2nd Edition, Springer, New York, 340 p. https://doi.org/10.1007/978-3-319-77586-9_9 |

Journals Menu

Contact us

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2023 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.