---
title: "4. Computational notes"
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{4. Computational notes}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r setup, include = FALSE}
knitr::opts_chunk$set(collapse = TRUE, comment = "#>", eval = FALSE)
```

This vignette explains how the estimation engine is actually computed, and why
the way it is computed is not the way the equations are written. The estimation
algorithms themselves -- the EM algorithm and where it is slow, ECME, SQUAREM,
the stopping rule and the limits of the range -- are described in the
Computational Supplement that ships with the package,
`system.file("extdata", "Stem-computational-supplement.pdf", package = "Stem")`,
and on the page `docs/computational-aspects.md` of the repository. None of it
changes the model or the estimator: every step below is an algebraic identity,
and the estimates it produces agree with the direct form to about $10^{-13}$ in
relative terms. What changes is what the package can fit at all.

The short version. A network of $d$ stations observed over $T$ periods used to
cost $O(T d^3)$ per pass of the Kalman filter, and to overflow the range of
double precision past a few hundred stations. It now costs $O(d^3 + T d^2)$ and
does not overflow. On 200 stations over a year an EM iteration is about ten
times faster; a 400-station network, which the direct form cannot fit at all,
takes about a second per iteration.

## 1. What "cost $O(T d^3)$" means

The **cost** of an algorithm is the number of elementary floating-point
operations it performs -- additions, multiplications, divisions. It is not a
time: the time depends on the machine. The $O(\cdot)$ notation says how that
work grows with the size of the problem, ignoring multiplicative constants and
lower-order terms.

**Why inverting a $d \times d$ matrix costs $O(d^3)$.** Not by cofactors, which
would cost $d!$. By factorization: an LU decomposition for a general matrix, a
Cholesky decomposition for a symmetric positive definite one. Gaussian
elimination proceeds column by column: at column $k$ it eliminates the $d-k$
entries below the pivot, and for each of those rows it updates a row of $d-k$
entries, which is $(d-k)^2$ operations. Summing over the columns,

$$\sum_{k=1}^{d}(d-k)^2 = \sum_{j=0}^{d-1}j^2 = \frac{d(d-1)(2d-1)}{6}\approx\frac{d^3}{3}$$

multiplications, and as many additions: about $\tfrac{2}{3}d^3$ operations for
the factorization. Cholesky, exploiting symmetry, costs half of that. Forming
the explicit inverse then needs $d$ triangular solves at $O(d^2)$ each, so
$O(d^3)$ again.

**Where the factor $T$ comes from.** The measurement equation of the model is

$$z_t = X_t\beta + A y_t + e_t, \qquad e_t \sim N_d(0, \Sigma_\varepsilon),$$

and the filter needs, at every time point, the covariance of the one-step-ahead
predictive distribution of $z_t$,

$$Q_t = A P_t A' + \Sigma_\varepsilon,$$

together with its inverse and its determinant. $P_t$, the predicted variance of
the state, changes with $t$, so $Q_t$ changes with $t$, so a direct
implementation factorizes a $d\times d$ matrix $T$ times per pass.

Concretely, at $d = 400$: $d^3 = 6.4\times 10^{7}$, so about $4\times 10^{7}$
operations per factorization, roughly $0.04$ seconds with the reference BLAS
that ships with R. That looks small. Multiplied by $T = 730$ it is 29 seconds
for **one forward pass**, that is one E-step; an EM run does thirty to fifty of
them; and `SCSTEM_Estimation()` runs an EM per regime, for every point of the
$(K,\varphi)$ grid, for every bootstrap draw. The cubic term is paid thousands
of times.

Doubling $d$ multiplies a quadratic cost by four and a cubic cost by eight.
Going from 200 to 400 stations does not double the work; it multiplies it by
eight. That is why the order matters more than the constant.

## 2. Why the Woodbury identity helps

$Q_t$ is not an arbitrary $d\times d$ matrix. Two facts about it are structural.

1. $\Sigma_\varepsilon = \sigma^2_\varepsilon I_d + \sigma^2_\omega C(h;\theta)$
   **does not depend on $t$**: it is a function of the parameters only, and is
   rebuilt once per EM iteration.
2. $A P_t A'$ **has rank $p$**, the dimension of the latent state, which is one
   in the default specification. Between one time point and the next, $d^2$
   numbers change, but with only $p(p+1)/2$ degrees of freedom.

The Woodbury identity says that the inverse of an invertible matrix plus a
low-rank update is the inverse of the first plus a low-rank correction:

$$(M + UCV)^{-1} = M^{-1} - M^{-1}U\,(C^{-1} + VM^{-1}U)^{-1}\,VM^{-1}.$$

With $M = \Sigma_\varepsilon$, $U = A$, $C = P_t$ and $V = A'$,

$$Q_t^{-1} = \Sigma_\varepsilon^{-1} - \Sigma_\varepsilon^{-1}A\,
             (P_t^{-1} + A'\Sigma_\varepsilon^{-1}A)^{-1}\,
             A'\Sigma_\varepsilon^{-1}.$$

The only inverse that depends on $t$ is that of
$P_t^{-1} + A'\Sigma_\varepsilon^{-1}A$, which is $p\times p$: with $p = 1$ it
is a division. Everything else -- the Cholesky factor of $\Sigma_\varepsilon$,
the product $A'\Sigma_\varepsilon^{-1}A$, the matrix
$\Sigma_\varepsilon^{-1}A$ -- is constant over the pass and computed once.

The determinant, needed for the log-likelihood, comes from the matrix
determinant lemma, which is the same statement about $\det$:

$$\log|Q_t| = \log|\Sigma_\varepsilon| + \log|P_t| +
              \log|P_t^{-1} + A'\Sigma_\varepsilon^{-1}A|,$$

again with only a $p\times p$ piece depending on $t$.

**And $Q_t$ itself is never needed.** The recursion uses only

- $A'Q_t^{-1}A$, which is $p\times p$,
- $A'Q_t^{-1}e_t$, which is $p\times 1$,
- the quadratic form $e_t'Q_t^{-1}e_t$, a scalar, obtained from one triangular
  solve against the cached Cholesky factor of $\Sigma_\varepsilon$ at $O(d^2)$,
  corrected by a $p\times p$ term.

So a pass costs $O(d^3)$ **once**, for the factorization of
$\Sigma_\varepsilon$, plus $O(d^2)$ per time point: $O(d^3 + T d^2)$ in place
of $O(T d^3)$.

## 3. Under what conditions

| Assumption | Status in this model |
|---|---|
| $\Sigma_\varepsilon$ does not depend on $t$ | **Holds.** It is $\sigma^2_\varepsilon I + \sigma^2_\omega\exp(-\theta h)$, a function of the parameters alone. Time-varying heteroskedasticity would destroy the gain. |
| The update has low rank, $p \ll d$ | **Holds.** $p = 1$ by default. The cost per step goes from $O(d^3)$ to $O(d^2 p + p^3)$, so at $p = d$ there is nothing to gain. |
| $\Sigma_\varepsilon$ and $P_t$ are invertible | **Automatic.** Both are positive definite by construction: the nugget $\sigma^2_\varepsilon > 0$ bounds the first away from singularity, and $P_t = G C_{t-1}G' + \Sigma_\eta$ inherits it from $\Sigma_\eta$. This is not an approximation: the identity is exact. |
| Numerical stability | Woodbury can be worse than a direct inverse when $A$ is ill-conditioned and the low-rank correction nearly cancels it. Here the nugget keeps the condition number bounded, and $\Sigma_\varepsilon^{-1}$ is never formed explicitly: the code carries the Cholesky factor and uses triangular solves. |
| Missing values | The constants depend on **which rows are observed**, so they are recomputed once per *distinct missingness pattern* rather than once per $t$. In a monitoring network a station is out of service for a stretch of consecutive days, so the distinct patterns are few and the cache almost always hits. A record in which every period had a different pattern would return to $O(T d^3)$. |

## 4. The log-density, which is a different problem

The likelihood term of period $t$ is the log of a Gaussian density on $d$
observations,

$$-\tfrac{1}{2}\left\{ d\log 2\pi + \log|Q_t| + e_t'Q_t^{-1}e_t \right\}.$$

Evaluating the **density** and taking its logarithm afterwards is not a matter
of speed. A Gaussian density on $d$ observations is of order $e^{-d}$; the
smallest positive normalized double is $2.2\times10^{-308} = e^{-708}$. Past a
few hundred stations the density underflows to exactly zero, its logarithm is
`-Inf`, and the EM algorithm stops. Computing the log-density directly never
touches the small number.

There is a speed argument as well, but it is secondary: `mvtnorm::dmvnorm()`
re-checks the symmetry of $Q$ with `all.equal()` on every call, which on a
36-station network was about a seventh of the total running time.

## 5. The M-step, written as matrix products

The sums the M-step accumulates over time are cross-products, not loops. Because
the loading matrix does not depend on time, the second moment of the measurement
error collapses to

$$\sum_t \left\{ A C^s_t A' + r_t r_t' \right\} = A\Big(\sum_t C^s_t\Big)A' + R'R,$$

with $R$ the $T\times d$ matrix of residuals: one cross-product in place of $T$
outer products, and no need to hold $T$ matrices of size $d\times d$ at once.
The three sums of outer products of the smoothed states are cross-products of
the $T\times p$ matrix of those states, and the two accumulations entering the
update of $\beta$,

$$M = \sum_t X_t'\Sigma_e^{-1}X_t, \qquad v = \sum_t X_t'\Sigma_e^{-1}v_t,$$

are cross-products of the design blocks stacked by period.

Finally, every trace of a matrix product is evaluated as

$$\operatorname{tr}(AB) = \sum_{i}\sum_{j} A_{ij}B_{ji},$$

which costs $O(d^2)$ and does not form the $O(d^3)$ product whose diagonal would
otherwise be read and discarded.

## 6. What it is worth

Ten EM iterations on a synthetic network generated from the model itself,
measured against the state of the code before these changes:

| $d$ | $T$ | before (s) | after (s) | speed-up | max relative difference |
|---:|---:|---:|---:|---:|---|
| 36 | 365 | 2.1 | 0.9 | 2.3x | 1.18e-13 |
| 60 | 365 | 2.1 | 0.6 | 3.3x | 7.96e-14 |
| 100 | 365 | 5.9 | 1.2 | 5.0x | 1.17e-13 |
| 200 | 365 | 15.5 | 1.6 | 9.8x | 2.85e-13 |
| 400 | 200 | *fails* | 10.8 | -- | reference underflows to `-Inf` |

The column that matters is the last one. Both changes are algebraic identities,
so the estimates coincide to floating point; the speed-up is the consequence,
not the claim. The benchmark reconstructed the previous sources from git and
ran the two side by side on the same data.

## 7. Where to look in the sources

| File | What it holds |
|---|---|
| `R/filterstep.R` | one step of the filter in Woodbury form, with the algebra and the superseded code in the header |
| `R/filtering.R` | the pass, and the cache of pattern constants |
| `R/kalman.R` | the Kalman filter, the fixed-interval smoother and the lag-one covariance smoother at given parameters |
| `R/estep.R` | the E-step: the expected sufficient statistics, with the cross-product accumulations |
| `R/mstep-updates.R`, `R/mstep-em.R`, `R/mstep-ecme.R` | the conditional updates of the M-step, and the M-steps of the EM and ECME algorithms |
| `R/squarem.R`, `R/em-fit.R` | the SQUAREM acceleration, and the wrapper that runs the algorithm chosen and applies the stopping rule |
| `R/d1_Q.R`, `R/d2_Q.R`, `R/d12_Q.R` | the derivatives of the objective, with the shared products |
| `R/Stem-02-internal.R` | the structured products used when a derivative is a multiple of the identity |
| `R/stem-penalty.R` | the regularized update of the coefficients, a separate matter |

The files of the filter and of the derivatives keep the expression they
replaced, commented, immediately above the expression that replaced it; the
E-step and the M-step were split out of `kalman()` into separate files in
version 2.0.0, and the code they replaced is in the history of the repository.

## References

Durbin, J., Koopman, S. J. (2012) *Time Series Analysis by State Space
Methods*, 2nd edition. Oxford University Press. Sections 2.7, 4.10 and 7.3 for
the treatment of missing observations.

Golub, G. H., Van Loan, C. F. (2013) *Matrix Computations*, 4th edition. Johns
Hopkins University Press. Chapters 2 and 4 for the operation counts and the
stability of the factorizations.

Henderson, H. V., Searle, S. R. (1981) *On deriving the inverse of a sum of
matrices*. SIAM Review, 23, 53--60. The history of the identity.
