4. Computational notes

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

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.