Is it possible to update a gaussian process individually for each observation?

Question

I am coding a simple univariate GP and was planning to update the posterior sequentially every time a new sample is taken. It is well known that for a partitioned Gaussian as follows

\begin{equation} \left(\begin{array}{l} y_{a} \\ y_{b} \end{array}\right) \sim N\left(\left(\begin{array}{l} \mu_{a} \\ \mu_{b} \end{array}\right), \left(\begin{array}{ll} \sum_{a a} & \sum_{a b} \\ \sum_{b a} & \sum_{b b} \end{array}\right)\right) \end{equation}

the conditional distribution is a Gaussian with mean and var given by

\begin{equation} \mu_{a|b}=\mu_a + \Sigma_{ab}\Sigma_{bb}^{-1}(y_b-\mu_b)\\ \Sigma_{a|b}=\Sigma_{aa}-\Sigma_{ab}\Sigma_{bb}^{-1}\Sigma_{ba} \end{equation}

where $\Sigma_{ab}=\Sigma_{ba}^T$ and $\Sigma$ is given by the kernel function of x values.

So in the Bayesian Optimization / GP context, $a$ would be the set of GP function values and $b$ the observed values. So if the values of $b$ are not given all at once, I would like to update the GP sequentially and keep an updated version of the GP at each step. My thinking was that the most computationally efficient approach would be to update it with each variable individually at each time step (as opposed to updating a growing vector of observed values and using this to update the original GP). This would remove the need to calculate $\Sigma_{bb}^{-1}$ for a growing vector.

Instead $\Sigma_{aa}$ would be updated at each iteration, essentially becoming $\Sigma_{(a|b_1)|b_2}$ for the second iteration. However since $\Sigma_{ab}$ and its transpose are calculated via the kernel function I'm confused if this makes sense and how I would even do it since I'm no longer referencing the x values used to create the initial $\Sigma_{aa}$. So do GPs have to be updated with all observed values only once? Then recalculated when a new observation is taken?

Answer 1

I think we can start with decomposing $b$ into two subsets $b_1$ and $b_2$. The resulting partitioned Gaussian is given by $$ \begin{pmatrix} y_a\\y_{b_1}\\y_{b_2}\end{pmatrix} \sim \mathcal{N}\left[\begin{pmatrix} \mu_a\\\mu_{b_1}\\\mu_{b_2}\end{pmatrix},\begin{pmatrix} \Sigma_{aa} & \Sigma_{ab_1} & \Sigma_{ab_2} \\ \Sigma_{b_1a} & \Sigma_{b_1b_1} & \Sigma_{b_1b_2} \\ \Sigma_{b_2a} & \Sigma_{b_2b_1} & \Sigma_{b_2b_2}\end{pmatrix}\right]. $$ The resulting posterior distribution for $y_a$ is given by $$ y_a \vert y_{b_1}, y_{b_2} \sim \mathcal{N}(\mu_{a\vert b_1, b_2}, \Sigma_{a\vert b_1, b_2}), $$ where $$ \mu_{a\vert b_1, b_2} = \mu_a + \Sigma_{ab}\Sigma^{-1}_{bb}(y_{b} - \mu_b), $$ $$ \Sigma_{a\vert b_1, b_2} = \Sigma_{aa} - \Sigma_{ab}\Sigma^{-1}_{bb}\Sigma_{ba}. $$ In which $$ \begin{aligned} y_b &= \begin{pmatrix} y_{b_1} \\ y_{b_2} \end{pmatrix},\\ \mu_b &= \begin{pmatrix} \mu_{b_1} \\ \mu_{b_2}\end{pmatrix},\\ \Sigma_{bb} &= \begin{pmatrix} \Sigma_{b_1b_1} & \Sigma_{b_2b_1} \\ \Sigma_{b_2b_1} & \Sigma_{b_2b_2} \end{pmatrix},\\ \Sigma_{ab} &= \begin{pmatrix} \Sigma_{ab_1} & \Sigma_{ab_2}\end{pmatrix}. \end{aligned} $$ Therefore, it is equivalent to considering $y_{b_1}$ and $y_{b_2}$ as one $y_b$ and do the calculation. One can obtain a more clear picture by revisiting the definition of conditional probability and the Bayes theorem; $$ \begin{aligned} p(y_a \vert y_{b_1}, y_{b_2}) &\propto p(y_{b_1}, y_{b_2} \vert y_a)p(y_a)\\ &= p(y_{b_2} \vert y_{b_1}, y_a)p(y_{b_1} \vert y_a)p(y_a)\\ &= p(y_{b_2} \vert y_{b_1}, y_a) p(y_a \vert y_{b_1}). \end{aligned} $$ Therefore to have a sequential update, you would need to calculate $p(y_{b_2} \vert y_{b_1}, y_a)$ every time you obtain a new observation, resulting in no computational advantage compared to calculating with all data at once.