Exploiting Sparsity in Batch Solution

From Batch Discrete-Time Estimation, we get alot of sparse matricies.

$$({\mathbf{H}}^T{\mathbf{W}}^{-1}\mathbf{H})\hat{\mathbf{x}}={\mathbf{H}}^T{\mathbf{W}}^{-1}\mathbf{z}$$

Here

$${\mathbf{H}}^T{\mathbf{W}}^{-1}\mathbf{H}=\left[\begin{array}{ccccccc}\ast & \ast & & & & & \\ \ast & \ast & \ast & & & & \\ & \ast & \ast & \ast & & & \\ & & \dots & \dots & & & \\ & & & \ast & \ast & \ast & \\ & & & & \ast & \ast & \end{array}\right]$$

Where * refers to non-zero blocks. This is known as a block-tridiagonal. Solvers implement efficient algs to do so underthehood, so its not too bad.

There are, however, a couple of theoretical ways to optimize this computation.

Using that, we can do a Cholesky Decomposition

$${\mathbf{H}}^T{\mathbf{W}}^{-1}\mathbf{H}=\mathbf{L}{\mathbf{L}}^T$$

Where $\mathbf{L}$ is a block-lower-tridiagonal matrix called the Cholesky Factor.

$$L=\left[\begin{array}{ccccccc}\ast & & & & & & \\ \ast & \ast & & & & & \\ & \ast & \ast & & & & \\ & & \dots & \dots & & & \\ & & & \ast & \ast & & \\ & & & & \ast & \ast & \end{array}\right]$$

Compute:

$$\mathbf{Ld}={\mathbf{H}}^T{\mathbf{W}}^{-1}\mathbf{z}$$ $${\mathbf{L}}^T\hat{\mathbf{x}}=\mathbf{d}$$

This makes the computation scale in linear time for the number of states.

This block-tridiagonal sparsity pattern makes possible a family of recursive solvers such as the Rauch-Tung-Striebel Smoother whose initial steps is a Kalman Filter