KL-optimal parameter reduction

We want to find the constrained GP with parameters ($\hat{{\boldsymbol { \alpha } }}_{t+1}^{}$,$\hat{{\boldsymbol { C } }}_{t+1}^{}$) with the last elements all having zero values (see Section 3.3) that minimises the KL-divergence

$$\begin{split}2&{\ensuremath{\mathrm{KL}}}(\hat{{\ensuremath{{... ...oldsymbol { K } }_{t+1}^{-1}\right)^{-1}\right\vert \end{split}$$ (196)

and we suppose the GP parameters ($\alpha$_{t + 1},C_{t + 1}) and the $\cal {BV}$ set are given (we know K_{t + 1} and K_t). In the following we use K_{t + 1}^-1 = Q_{t + 1} and the decomposition of the GP parameters as presented in Chapter 3, with Fig 3.3 repeated in Fig D.1.

Figure: Grouping of the GP parameters (Fig 3.3 repeated).

The differentiation with respect to parameters $\hat{\alpha}_{1}^{}$,...,$\hat{\alpha}_{t}^{}$ leads to the system of equations that is easily written in matrix form as

$$\begin{split}\begin{bmatrix}{\boldsymbol { I } }_t & {\boldsy... ...{t+1} - {\boldsymbol { \alpha } }_{t+1} \right) &=0 \end{split}$$ (197)

where I_t is the identity matrix and 0_t is the column vector of length t with zero elements. In the second line the matrix multiplication has been performed and we used the decomposition

$$\left(\vphantom{{\boldsymbol { Q } }_{t+1} + {\boldsymbol { C } }_{t+1}}\right. \left.\vphantom{{\boldsymbol { Q } }_{t+1} + {\boldsymbol { C } }_{t+1}}\right)^{-1}_{} \begin{bmatrix}{\boldsymbol { B } }& {\boldsymbol { a } }\\ {\boldsymbol { a } }^T & b \end{bmatrix}$$ (198)

Finally, using the decomposition of the vector $\alpha$_{t + 1} from Fig. 3.3, we have

$$\hat{{\boldsymbol { \alpha } }}_{t+1}^{} \alpha \alpha^{*}_{} \tilde{{\boldsymbol { e } }}_{t+1}^{} \tilde{{\boldsymbol { e } }}_{t+1}^{}$$

and $\tilde{{\boldsymbol { e } }}_{t+1}^{}$ is obtained from the matrix inversion lemma for block matrices from eq. (182). Using the matrix inversion lemma for (Q_{t + 1} + C_{t + 1})^-1 from eq. (198) we have:

$$\begin{bmatrix}\left( {\boldsymbol { B } }-\frac{{\boldsymbol { a... ... -{\boldsymbol { a } }^T{\boldsymbol { B } }^{-1}\delta & \delta \end{bmatrix} \delta \left(\vphantom{b - {\boldsymbol { a } }^T{\boldsymbol { B } }{\boldsymbol { a } }}\right. \left.\vphantom{b - {\boldsymbol { a } }^T{\boldsymbol { B } }{\boldsymbol { a } }}\right)^{-1}_{}$$ (199)

and using the correspondence $\delta$ = q^* + c^* and Q^* + C^* = - B^-1a$\delta$ read from eq. (199), we have

$$\tilde{{\boldsymbol { e } }}_{t+1}^{} {\frac{1}{q^* + c^*}} \left(\vphantom{{\boldsymbol { Q } }^* + {\boldsymbol { C } }^* }\right. \left.\vphantom{{\boldsymbol { Q } }^* + {\boldsymbol { C } }^* }\right)$$ (200)

and replacing it into the expression for the reduced mean parameters, we have

$$\hat{{\boldsymbol { \alpha } }}_{t+1}^{} \alpha^{(r)}_{} {\frac{\alpha^*}{c^* + q^*}} \left(\vphantom{{\boldsymbol { Q } }^* + {\boldsymbol { C } }^* }\right. \left.\vphantom{{\boldsymbol { Q } }^* + {\boldsymbol { C } }^* }\right)$$ (201)

$\qedsymbol$

Before differentiating the KL-divergence with respect to $\hat{{\boldsymbol { C } }}_{t+1}^{}$, we simplify the terms that include $\hat{{\boldsymbol { C } }}_{t+1}^{}$ in eq. (196). Firstly we write the constraints for the last row and column of $\hat{{\boldsymbol { C } }}_{t+1}^{}$ using the extension matrix [I_t  0_t] as

$$\hat{{\boldsymbol { C } }}_{t+1}^{} \begin{bmatrix}{\boldsymbol { I } }_t & {\boldsymbol { 0 } }_t \end{bmatrix}^{T}_{} \hat{{\boldsymbol { C } }}_{t+1}^{(r)} \begin{bmatrix}{\boldsymbol { I } }_t & {\boldsymbol { 0 } }_t \end{bmatrix}$$ (202)

where $\hat{{\boldsymbol { C } }}_{t+1}^{(r)}$ is a matrix with t rows and columns, and in the following we will use $\hat{{\boldsymbol { C } }}_{t+1}^{}$ instead of $\hat{{\boldsymbol { C } }}_{t+1}^{(r)}$. Permuting the elements in the trace term of eq. (196) leads to

$$\left[\vphantom{\begin{bmatrix}{\boldsymbol { I } }_t & {\boldsym... ...d{bmatrix}({\boldsymbol { C } }_{t+1}+{\boldsymbol { Q } }_{t+1})^{-1} }\right. \begin{bmatrix}{\boldsymbol { I } }_t & {\boldsymbol { 0 } }_t\end{bmatrix}^{T}_{} \hat{{\boldsymbol { C } }}_{t+1}^{} \begin{bmatrix}{\boldsymbol { I } }_t & {\boldsymbol { 0 } }_t\end{bmatrix} \left.\vphantom{\begin{bmatrix}{\boldsymbol { I } }_t & {\boldsym... ...d{bmatrix}({\boldsymbol { C } }_{t+1}+{\boldsymbol { Q } }_{t+1})^{-1} }\right]$$

$$= \ensuremath{\mathrm{tr}}\left[\hat{{\boldsymbol { C } }}_{t+1} \b... ...{bmatrix}{\boldsymbol { I } }_t & {\boldsymbol { 0 } }_t\end{bmatrix}^T \right]$$ (203)

where the additive term - C_{t + 1}(C_{t + 1} + Q_{t + 1})^-1 is ignored since it will not contribute to the result of the differentiation. Ignoring also the term not depending on $\hat{{\boldsymbol { C } }}_{t+1}^{}$ in the determinant, and using the replacement of $\hat{{\boldsymbol { C } }}_{t+1}^{}$ from eq. (202) we simplify the log-determinant

$$\left\vert\vphantom{\left(\begin{bmatrix}{\boldsymbol { I } }_t &... ... {\boldsymbol { 0 } }_t\end{bmatrix}+{\boldsymbol { Q } }_{t+1}\right) }\right. \left(\vphantom{\begin{bmatrix}{\boldsymbol { I } }_t & {\boldsym... ... } }_t & {\boldsymbol { 0 } }_t\end{bmatrix}+{\boldsymbol { Q } }_{t+1}}\right. \begin{bmatrix}{\boldsymbol { I } }_t & {\boldsymbol { 0 } }_t\end{bmatrix}^{T}_{} \hat{{\boldsymbol { C } }}_{t+1}^{} \begin{bmatrix}{\boldsymbol { I } }_t & {\boldsymbol { 0 } }_t\end{bmatrix} \left.\vphantom{\begin{bmatrix}{\boldsymbol { I } }_t & {\boldsym... ... } }_t & {\boldsymbol { 0 } }_t\end{bmatrix}+{\boldsymbol { Q } }_{t+1}}\right) \left.\vphantom{\left(\begin{bmatrix}{\boldsymbol { I } }_t & {\b... ...oldsymbol { 0 } }_t\end{bmatrix}+{\boldsymbol { Q } }_{t+1}\right) }\right\vert \left\vert\vphantom{ \begin{bmatrix} \hat{{\boldsymbol { C } }}_{... ...{\boldsymbol { Q } }^*\\ {\boldsymbol { Q } }^{*T} & q^* \end{bmatrix}}\right. \begin{bmatrix} \hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol {... ...{q^*} & {\boldsymbol { Q } }^*\\ {\boldsymbol { Q } }^{*T} & q^* \end{bmatrix} \left.\vphantom{ \begin{bmatrix} \hat{{\boldsymbol { C } }}_{t+1}... ...ldsymbol { Q } }^*\\ {\boldsymbol { Q } }^{*T} & q^* \end{bmatrix}}\right\vert$$ =

$$\left\vert\vphantom{ \hat{{\boldsymbol { C } }}_{t+1} + {\boldsym... ...T}}{q^*} - \frac{{\boldsymbol { Q } }^*{\boldsymbol { Q } }^{*T}}{q^*} }\right. \hat{{\boldsymbol { C } }}_{t+1}^{} {\frac{{\boldsymbol { Q } }^*{\boldsymbol { Q } }^{*T}}{q^*}} {\frac{{\boldsymbol { Q } }^*{\boldsymbol { Q } }^{*T}}{q^*}} \left.\vphantom{ \hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol ... ...q^*} - \frac{{\boldsymbol { Q } }^*{\boldsymbol { Q } }^{*T}}{q^*} }\right\vert$$ =

$$\left\vert\vphantom{ \hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_t }\right. \hat{{\boldsymbol { C } }}_{t+1}^{} \left.\vphantom{ \hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_t }\right\vert$$ = (204)

where we used the decomposition into block-diagonal matrices (first line) and the expression for the determinants of block-diagonal matrices from eq (184).

The differentiation of the KL-distance with respect to $\hat{{\boldsymbol { C } }}_{t+1}^{}$ is the addition of differentiating eqs. (203) and (204):

$$\left(\vphantom{ \hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_{t} }\right. \hat{{\boldsymbol { C } }}_{t+1}^{} \left.\vphantom{ \hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_{t} }\right)^{-1}_{} \begin{bmatrix}{\boldsymbol { I } }_t & {\boldsymbol { 0 } } \end{bmatrix} \left(\vphantom{{\boldsymbol { Q } }_{t+1} + {\boldsymbol { C } }_{t+1}}\right. \left.\vphantom{{\boldsymbol { Q } }_{t+1} + {\boldsymbol { C } }_{t+1}}\right)^{-1}_{} \begin{bmatrix}{\boldsymbol { I } }_t & {\boldsymbol { 0 } } \end{bmatrix}^{T}_{}$$ (205)

We apply the matrix inversion lemma to the RHS similarly to the case of eq (204) and retaining only the upper-left part leads to

$$\left(\vphantom{\hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_t }\right. \hat{{\boldsymbol { C } }}_{t+1}^{} \left.\vphantom{\hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_t }\right)^{-1}_{} \left(\vphantom{{\boldsymbol { C } }^{(r)} + {\boldsymbol { Q } }... ...t({\boldsymbol { C } }^*+ {\boldsymbol { Q } }^*\right)^{T}} {q^*+c^*} }\right. {\frac{\displaystyle{\boldsymbol { Q } }^*{\boldsymbol { Q } }^{*T}}{q^*}} {\frac{\displaystyle\left({\boldsymbol { C } }^*+ {\boldsymbol { ... ...ight)\left({\boldsymbol { C } }^*+ {\boldsymbol { Q } }^*\right)^{T}}{q^*+c^*}} \left.\vphantom{{\boldsymbol { C } }^{(r)} + {\boldsymbol { Q } }... ...symbol { C } }^*+ {\boldsymbol { Q } }^*\right)^{T}} {q^*+c^*} }\right)^{-1}_{}$$ (206)

and the reduced covariance parameter is

$$\hat{{\boldsymbol { C } }}_{t+1}^{} {\frac{{\boldsymbol { Q } }^*{\boldsymbol { Q } }^{*T}}{q^*}} {\frac{\left({\boldsymbol { Q } }^*+{\boldsymbol { C } }^*\right)\left({\boldsymbol { Q } }^*+{\boldsymbol { C } }^*\right)^T}{q^* + c^*}}$$ (207)

$\qedsymbol$

ARRAY(0x896d3ec)ARRAY(0x896d3ec)

Computing the KL-distance

We are assessing the error made when pruning the GP by evaluating the KL-divergence from eq. (196) between the process with ($\alpha$_{t + 1},C_{t + 1}) and the pruned one with ($\hat{{\boldsymbol { \alpha } }}_{t+1}^{}$,$\hat{{\boldsymbol { C } }}_{t+1}^{}$) from the previous section. We start by writing the pruning equations in function of t + 1-dimensional vectors: in the following we will use Q^* $\doteq$ [Q^*Tq^*]^T and C^* $\doteq$ [C^*Tc^*]^T and the pruning equations are

$$\begin{split}\hat{{\boldsymbol { \alpha } }}_{t+1} &= {\bolds... ...oldsymbol { Q } }^*+{\boldsymbol { C } }^*\right)^T \end{split}$$ (208)

and it is easy to check that the updates will result in the last row and column being all zeros. In computing the KL-divergence we will use the identities from the matrix algebra:

$$\left(\vphantom{ {\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1} }\right. \left.\vphantom{ {\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1} }\right)^{-1}_{} \left(\vphantom{{\boldsymbol { C } }^* + {\boldsymbol { Q } }^* }\right. \left.\vphantom{{\boldsymbol { C } }^* + {\boldsymbol { Q } }^* }\right)$$

Based on the first identity, the term containing the mean is

$$\alpha \hat{{\boldsymbol { \alpha } }}_{t+1}^{} \left(\vphantom{{\boldsymbol { C } }_{t+1} + {\boldsymbol { K } }_{t+1}^{-1} }\right. \left.\vphantom{{\boldsymbol { C } }_{t+1} + {\boldsymbol { K } }_{t+1}^{-1} }\right)^{-1}_{} \alpha \hat{{\boldsymbol { \alpha } }}_{t+1}^{} {\frac{\alpha^{*2}}{q^* + c^*}}$$ (209)

The logarithm of the determinants is transformed, using the determinants of the block-diagonal matrices, in eq. (184):

$$\begin{split}\left\vert \hat{{\boldsymbol { C } }}_{t+1} + {\... ...*+{\boldsymbol { C } }^*\right)^T \right\vert\; q^* \end{split}$$ (210)

and using a similar decomposition for the denominator we have

$$\begin{split}\left\vert {\boldsymbol { C } }_{t+1} + {\boldsy... ...ymbol { C } }^*\right)^T \right\vert \; (q^* + c^*) \end{split}$$ (211)

and the logarithm of the ratio has the simple expression as

$$\left\vert\vphantom{ \left(\hat{{\boldsymbol { C } }}_{t+1} + {\b... ...ft({\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1}\right)^{-1} }\right. \left(\vphantom{\hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_{t+1}}\right. \hat{{\boldsymbol { C } }}_{t+1}^{} \left.\vphantom{\hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_{t+1}}\right) \left(\vphantom{ {\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1} }\right. \left.\vphantom{ {\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1} }\right)^{-1}_{} \left.\vphantom{ \left(\hat{{\boldsymbol { C } }}_{t+1} + {\bolds... ...\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1}\right)^{-1} }\right\vert {\frac{q^*}{q^* + c^*}}$$ (212)

Finally, using the invariance of the trace of a product with respect to circular permutation of its elements, the trace term is:

$$\left[\vphantom{ \left( \frac{{\boldsymbol { Q } }^*{\boldsymbol ... ...eft({\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1}\right)^{-1}}\right. \left(\vphantom{ \frac{{\boldsymbol { Q } }^*{\boldsymbol { Q } }... ...ft({\boldsymbol { Q } }^*+{\boldsymbol { C } }^*\right)^T} {q^* + c^*} }\right. {\frac{{\boldsymbol { Q } }^*{\boldsymbol { Q } }^{*T}}{q^*}} {\frac{\left({\boldsymbol { Q } }^*+{\boldsymbol { C } }^*\right)\left({\boldsymbol { Q } }^*+{\boldsymbol { C } }^*\right)^T}{q^* + c^*}} \left.\vphantom{ \frac{{\boldsymbol { Q } }^*{\boldsymbol { Q } }... ...ft({\boldsymbol { Q } }^*+{\boldsymbol { C } }^*\right)^T} {q^* + c^*} }\right) \left(\vphantom{ {\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1} }\right. \left.\vphantom{ {\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1} }\right)^{-1}_{} \left.\vphantom{ \left( \frac{{\boldsymbol { Q } }^*{\boldsymbol ... ...eft({\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1}\right)^{-1}}\right]$$

$$= \frac{1}{q^*}{\boldsymbol { Q } }^{*T}\left({\boldsymbol { C } }_... ... }_{t+1}\right)^{-1} \left({\boldsymbol { Q } }^*+{\boldsymbol { C } }^*\right)$$

$$= \frac{1}{q^*}{\boldsymbol { Q } }^{*T}\left[{\boldsymbol { K } }_... ...}_{t+1}\right)^{-1} {\boldsymbol { K } }_{t+1} \right]{\boldsymbol { Q } }^* -1$$

$$= 1 - \frac{1}{q^*}{\boldsymbol { e } }_{t+1}^T \left({\boldsymbol ... ...}{\boldsymbol { e } }_{t+1} - 1 = - \frac{\displaystyle s^*}{\displaystyle q^*}$$ (213)

where s^* is the last diagonal element of the matrix (C_{t + 1}^-1 + K_{t + 1})^-1. Summing up eqs (209), (212), and (213), we have the minimum KL-distance

$$\hat{{\ensuremath{{\cal{GP}}}}}_{t+1}^{} \cal {GP} {\frac{\alpha^{*2}}{q^* + c^*}} {\frac{s^*}{q^*}} \left(\vphantom{ 1+ \frac{c^*}{q^*}}\right. {\frac{c^*}{q^*}} \left.\vphantom{ 1+ \frac{c^*}{q^*}}\right)$$ (214)

Updates for S_{t + 1} = (C_{t + 1}^-1 + K_{t + 1})^-1

Matrix inversion is a sensitive issue and we are trying to avoid it. In computing the score for a given $\cal {BV}$ in the previous section, eq. (214), we need the diagonal element of the matrix S = (C^-1 + K)^-1. In this section we sketch an iterative update rule for the matrix S, and an update when the KL-optimal removal of the last $\cal {BV}$ element is performed.

First we establish the update rules for the inverse of matrix C_{t + 1}. By using the matrix inversion lemma and the update from eq. (57), the matrix C^-1 is

$$\begin{bmatrix}{\boldsymbol { C } }_t^{-1} & -{\boldsymbol { k } ... ...l { k } }_{t+1}^T{\boldsymbol { C } }_t{\boldsymbol { k } }_{t+1} \end{bmatrix}$$ (215)

then we combine the above relation with the block-diagonal decomposition of the kernel matrix, and observing that the t×1 column vector is zero, we have

$$\left(\vphantom{{\boldsymbol { C } }_{t+1}^{-1} + {\boldsymbol { K } }_{t+1} }\right. \left.\vphantom{{\boldsymbol { C } }_{t+1}^{-1} + {\boldsymbol { K } }_{t+1} }\right)^{-1}_{} \begin{bmatrix}\left({\boldsymbol { C } }_t^{-1}+{\boldsymbol { K... ...)^{-1} & {\boldsymbol { 0 } } \\ {\boldsymbol { 0 } }^T & a^{-1} \end{bmatrix}$$

and this shows that the update for the matrix S_{t + 1} is particularly simple: we only need to add a value on the last diagonal element.

When removing a $\cal {BV}$ however, the resulting matrix will not be diagonal any more. To have an update quadratic in the size of S, we use the matrix inversion lemma

$$\left(\vphantom{ {\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1} }\right. \left.\vphantom{ {\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1} }\right)^{-1}_{}$$

and after the pruning we are looking for the t×t matrix $\hat{{\boldsymbol { S } }}_{t+1}^{}$ = $\left(\vphantom{\hat{{\boldsymbol { C } }}_{t+1}^{-1}+{\boldsymbol { K } }_t}\right.$$\hat{{\boldsymbol { C } }}_{t+1}^{-1}$ + K_t$\left.\vphantom{\hat{{\boldsymbol { C } }}_{t+1}^{-1}+{\boldsymbol { K } }_t}\right)^{-1}_{}$. We can obtain this by using eq. (206): the pruned $\left(\vphantom{\hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_{t}}\right.$$\hat{{\boldsymbol { C } }}_{t+1}^{}$ + Q_t$\left.\vphantom{\hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_{t}}\right)^{-1}_{}$ is the matrix obtained by cutting the last row and column from $\left(\vphantom{{\boldsymbol { C } }_{t+1}+{\boldsymbol { Q } }_{t+1}}\right.$C_{t + 1} + Q_{t + 1}$\left.\vphantom{{\boldsymbol { C } }_{t+1}+{\boldsymbol { Q } }_{t+1}}\right)^{-1}_{}$. The computation of the updated matrix $\hat{{\boldsymbol { S } }}_{t+1}^{}$ has thus three steps:

1. compute

   $$\left(\vphantom{ {\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1} }\right. \left.\vphantom{ {\boldsymbol { C } }_{t+1} + {\boldsymbol { Q } }_{t+1} }\right)^{-1}_{}$$

   
   

2. compute the reduced matrix $\left(\vphantom{\hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_{t}}\right.$$\hat{{\boldsymbol { C } }}_{t+1}^{}$ + Q_t$\left.\vphantom{\hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_{t}}\right)^{-1}_{}$ by trimming, use eq. (206)
3. compute the updated $\hat{{\boldsymbol { S } }}_{t+1}^{}$ using

   $$\hat{{\boldsymbol { S } }}_{t+1}^{} \left(\vphantom{ \hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_{t} }\right. \hat{{\boldsymbol { C } }}_{t+1}^{} \left.\vphantom{ \hat{{\boldsymbol { C } }}_{t+1} + {\boldsymbol { Q } }_{t} }\right)^{-1}_{}$$