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)\) - μ)\)\)\(,\)\)\)

x

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

Examples

Initialize

<< FGN.m

<< FitARMA.m

<< Statistics`

ARMA Simulation Example

m = 200; n1 = 200; n = n1 + m; Muz = 0. ;
r = TacvfARMA[phi, theta, n];
phi = {1.2399401603634308, -0.2653412932838738};
theta = {0.8436410920940121};
z = SimulateGaussianARMA[phi, theta, n];
z1 = Take[z, n1];

k = 1;
znew = Drop[z, n1];
zF = vF = Array[0 &, m];
G = toe[Take[r, n1]];
gk = Take[Drop[r, 1], n1];
GI = TrenchInverse[G];
zF[[1]] = 
        Muz + Reverse[gk] . GI . (z1 - Muz);
vF[[1]] = 
        r[[1]] - 
          gk . GI . gk;
zk = z1;

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

{Mean[errMMSE = (((znew - zF))^2)], 
      Mean[errM = (((znew - Mean[z1]))^2)], 
      MeanDifferenceCI[errMMSE, errM]}

Short[vF, 3]

FGN Simulation Example

m = 200; n1 = 200; n = n1 + m; H = 0.8; 
    Muz = 0. ;
r = Table[FGNAcf[k, H], {k, 0, n - 1}];
z = SimulateFGN[H, n];
z1 = Take[z, n1];

k = 1;
znew = Drop[z, n1];
zF = vF = Array[0 &, m];
G = toe[Take[r, n1]];
gk = Take[Drop[r, 1], n1];
GI = TrenchInverse[G];
zF[[1]] = 
        Muz + Reverse[gk] . GI . (z1 - Muz);
vF[[1]] = 
        r[[1]] - 
          gk . GI . gk;
zk = z1;

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

{Mean[errMMSE = (((znew - zF))^2)], 
      Mean[errM = (((znew - Mean[z1]))^2)], 
      MeanDifferenceCI[errMMSE, errM]}

Short[vF, 3]

Application to Nile Minimums

Percival & Walden comment in Sec 5.7 (p. 190), "Toussoun's record extends up to 1921.  It is complete for 622-1284.  For 1285-1470 there are scattered missing values."  We linearly interpolated to complete the record.

Initialize

z = ReadData["d:/math/2006/Trench/data/Minimum.1"];

n1 = 1284 - 622 + 1;

n = Length[z];

m = n - n1;

z1 = Take[z, n1];

FGN Case

ans = FitFGN[z1, MeanMLEQ -> True]

Hz = HurstCoefficient /. Last[ans];
Muz = MuHat /. Last[ans];
r = Table[FGNAcf[i - 1, Hz], {i, n}];

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[γ, k]),  k = 0,  ... , n - 1.  Then \(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 my be written \(TraditionalForm\`\(\(z\&^\)\_\(n + j\)\)(k) = μ + 
          g\_\(n, j\)\ \(\(Γ\_\(n + j\)\%\(-1\)\)(
              z\^\((n + j)\) - μ)\), \ 
      where\ g\_\(n, j\) = \ \((γ\_\(n + j + k - 2\)\ , \  ... \ , \ γ\_k)\)\) and (z^((n + j))) = ((Subscript[z, 1]),   ...  ,  
          (Subscript[z, n + j - 1])).  Rather than evaluating m matrix inverses of dimension n, n + 1,  n + m - 1 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.

k = 1;
znew = Drop[z, n1];
zF = Array[0 &, m];
G = toe[Take[r, n1]];
gk = Take[Drop[r, 1], n1];
zF[[1]] = 
        Muz + Reverse[gk] . 
            TrenchInverse[G] . (z1 - Muz);
zk = z1;

Do[
gk = 
          Append[gk, 
            r[[n1 + j - 
                1]]]; 
zk = 
          Append[zk, 
            z[[n1 + j - 
                1]]]; 
Ginv = 
          TrenchInverseUpdate[{r[[
                n1 + j]]}]; 
zF[[j]] = 
          Muz + Reverse[gk] . Ginv . (zk - Muz);, 
{j, 
          2, m}];

{Mean[errMMSE = (((znew - zF))^2)], 
      Mean[errM = (((znew - Mean[z1]))^2)], 
      MeanCI[errMMSE - errM]}

ARMA Forecast

ans = FitARMA[z, {2, 0, 1}];
CoefARMA[ans]

phi = Take[ARMACoefficients /. ans, 2];
theta = Drop[ARMACoefficients /. ans, 2];
Muz = MeanValue /. ans;

r = TacvfARMA[phi, theta, n];

k = 1;
znew = Drop[z, n1];
zF = Array[0 &, m];
G = toe[Take[r, n1]];
gk = Take[Drop[r, 1], n1];
zF[[1]] = 
        Muz + Reverse[gk] . 
            TrenchInverse[G] . (z1 - Muz);
zk = z1;

Do[
gk = 
          Append[gk, 
            r[[n1 + j - 
                1]]]; 
zk = 
          Append[zk, 
            z[[n1 + j - 
                1]]]; 
Ginv = 
          TrenchInverseUpdate[{r[[
                n1 + j]]}]; 
zF[[j]] = 
          Muz + Reverse[gk] . Ginv . (zk - Muz);, 
{j, 
          2, m}];

{Mean[errMMSE = (((znew - zF))^2)], 
      Mean[errM = (((znew - Mean[z1]))^2)], 
      MeanCI[errMMSE - errM]}