Application of the Trench Algorithm to Forecasting

Let \(TraditionalForm\`\(z\&^\_n\)(k)\) denote the minimum mean square error linear predictor of (Subscript[z, n + k]) given the data z = ((Subscript[z, 1]),   ...  ,  (Subscript[z, n])) and the autocovariances (Subscript[γ, l]),  l = 0,  ... , n - 1.  Then as shown by Hamilton (1994, §4.3) the finite-sample predictor may be written

\(TraditionalForm\`\(z\&^\_n\)(k) = μ + 
          g\_k\ \(\(Γ\_n\%\(-1\)\)(z - μ)\)\)

where \(TraditionalForm\`g\_k\  = \ \((γ\_\(n + k - 1\)\ , \  ... \ , \ γ\_k)\)\) and \(TraditionalForm\`var(\(z\&^\_n\)(k))\  = γ\_0\  - \ 
          g\_k\%\(\(\ \)\(T\)\)\ \(Γ\_n\%\(-1\)\) g\_k\).  In many forecasting applications, a model is fitted to the data to the first n observed time series values and then k-step ahead forecasting are needed for each of m additional observations, ((Subscript[z, n + 1]),   ...  ,  (Subscript[z, n + m])).  These forecasts may be written

\(TraditionalForm\`\(\(\(z\&^\_\(n + l\)\)(k) = μ + 
          g\_\(n, l\)\ \(\(Γ\_\(n + j\)\%\(-1\)\)(
              z\^\((n + l)\) - μ)\)\)\(,\)\)\)

where \(TraditionalForm\`\(\(\ \)\(g\_\(n, l\) = \ \((γ\_\(n + l + k - 2\)\ , \  ... \ , \ γ\_k)\)\)\)\) and (z^((n + l))) = ((Subscript[z, 1]),   ...  ,  
          (Subscript[z, n + l - 1])).  Rather than evaluating m matrix inverses of dimension n + 1,  ... ,  n + m we just need to evaluate (Subscript[Γ, n]^(-1)) and the remaining inverses can be obtained by updating our comptations.  This effectively reduces the matrix inverse computations from O(((m(n + m))^2)) flops to just O(n (n + m)) flops.  Hamilton (1994, §4.4) discusses the use of the Cholesky decomposition for finite sample forecast updating but the Trench algorithm provides a more computationally efficient approach.

More generally, we may be interested in computing the k-step predictor for k = 1, ⋯, L.  The vector of forecasts \(TraditionalForm\`\(z\&^\)\_n\%\((L)\) = \((\(z\_n\)(
            1), ⋯, \ \(z\_n\)(L))\)\) may be written,

\(TraditionalForm\`\(z\&^\)\_n\%\((L)\) = μ + 
          G\_L\ \(\(Γ\_n\%\(-1\)\)(z - μ)\)\)

where \(TraditionalForm\`\(\(G\_L = \((γ\_\(n + i - j\))\)\_\(n×L\)\)\(,\)\)\) where i = 1, ⋯, L and j = 1, ⋯, n.  For updating we can write,

\(TraditionalForm\`\(\(\(z\&^\)\_\(n + l\)\%\((L)\) = μ + 
          G\_\(L, l\)\ \(\(Γ\_\(n + l\)\%\(-1\)\)(
              z\^\((n + l)\) - μ)\)\)\(,\)\)\)

where \(TraditionalForm\`\(\(G\_\(L, l\) = \((γ\_\(n + l + i - j - 1\))\)\_\(\((n + l - 1)\)×L\)\)\(,\)\)\) where i = 1, ⋯, L and j = 1, ⋯, n + l - 1.

Hamilton, J.D. (1994).  Time Series Analysis.  New Jersey: Princeton University Press.

Examples

Initialize

<< FGN.m

<< FitARMA.m

<< Statistics`

ARMA Simulation Example

m = 100; n = 200; ℕ = n + m; Muz = 0. ; 
    phi1 = 0.8; phi = {phi1}; theta = {};
maxLead = 7;
SeedRandom[72177791];
r = TacvfARMA[phi, theta, ℕ];
zTOT = 
        SimulateGaussianARMA[phi, 
          theta, ℕ];
z = Take[zTOT, n];
zFF = vFF = 
          Table[0, {maxLead}, {m + 1}];
ans = Array[0 &,  maxLead];

\(Do[
znew = Drop[zTOT, n]; 
zF = \(vF = Array[0 &, m + 1]\); 

      G = toe[Take[r, n]]; 
gk = Take[Drop[r, k], n]; 

      GI = TrenchInverse[G]; 

      zF[[1]] = 
        Muz + Reverse[gk] . GI . \((z - Muz)\); 

      vF[[1]] = 
        r[[1]] - gk . GI . gk; 

      zk = z; 
VarF = Total[Table[phi1\^\(2  i\), {i, 0, k - 1}]]; 

      Do[
gk = 
          Append[gk, 
            r[[n + j - 
                1]]]; 
zk = 
          Append[zk, 
            zTOT[[n + j - 
                1]]]; 
GI = 
          TrenchInverseUpdate[{r[[
                n + j]]}]; 
zF[[j]] = 
          Muz + Reverse[gk] . 
              GI . \((zk - Muz)\); 
vF[[
            j]] = 
          r[[1]] - 
            gk . GI . gk; , 
{j, 2, m + 1}]; 

      ans[[k]] = {Mean[
            errMMSE = \((Drop[znew, k - 1] - Drop[zF, \(-k\)])\)\^2], 
          MeanCI[errMMSE], VarF}; 

      zFF[[k]] = zF; 

      vFF[[k]] = 
        vF; 
Print[" ok done. lead time: ", 
        k];
, {k, maxLead}]\)

\(TableForm[ans, TableDepth -> 2, 
      TableHeadings -> {None, {"Emp MSE", "C.I.", "MSE"}}]\)