Anisotropic Template Ansätze for Robust Positive Invariance under State-Dependent Uncertainty

Goal. Show that $\rho_{\bar{\boldsymbol{\Omega}}} := \sup_{\mathbf{e} \in \bar{\boldsymbol{\Omega}}} \gamma_{\bar{\boldsymbol{\Omega}}}(\mathbf{A}_{\mathrm{cl}} \mathbf{e}) < 1$.

Step 1 (RPI implies Pontryagin containment). By definition, $\bar{\boldsymbol{\Omega}}$ is RPI for $(\mathbf{A}_{\mathrm{cl}}, \bar{\mathbf{W}})$ means:

By the definition of the Pontryagin difference, $A \oplus B \subseteq C$ if and only if $A \subseteq C \ominus B$. Applying this with $A = \mathbf{A}_{\mathrm{cl}}\bar{\boldsymbol{\Omega}}$, $B = \bar{\mathbf{W}}$, $C = \bar{\boldsymbol{\Omega}}$:

Step 2 (Interior point implies strict erosion). Since $\mathbf{0} \in \mathrm{int}(\bar{\mathbf{W}})$, there exists $\varepsilon > 0$ such that $\varepsilon \mathcal{B}_2^n \subseteq \bar{\mathbf{W}}$. A classical result in set-valued analysis (see Blanchini, Proposition 3.2) states that for compact convex $\bar{\boldsymbol{\Omega}}$ and $\bar{\mathbf{W}}$ with $\mathbf{0} \in \mathrm{int}(\bar{\mathbf{W}})$:

for some $\delta > 0$. Intuitively, eroding $\bar{\boldsymbol{\Omega}}$ by a set with nonempty interior strictly shrinks it.

Step 3 (Derive the $\delta$ explicitly). To see why $\delta$ exists: for any $\mathbf{e} \in \bar{\boldsymbol{\Omega}} \ominus \bar{\mathbf{W}}$, we have $\mathbf{e} + \bar{\mathbf{W}} \subseteq \bar{\boldsymbol{\Omega}}$. In particular, $\mathbf{e} + \varepsilon \mathcal{B}_2^n \subseteq \bar{\boldsymbol{\Omega}}$, so $\mathbf{e}$ is at least distance $\varepsilon$ from the boundary of $\bar{\boldsymbol{\Omega}}$ (in the gauge metric). Since $\bar{\boldsymbol{\Omega}}$ is compact and contains the origin in its interior, let $R := \sup_{\mathbf{e} \in \bar{\boldsymbol{\Omega}}} \|\mathbf{e}\|_2$ be the circumradius. Then $\gamma_{\bar{\boldsymbol{\Omega}}}(\mathbf{e}) \le 1 - \varepsilon/R$ for all $\mathbf{e} \in \bar{\boldsymbol{\Omega}} \ominus \bar{\mathbf{W}}$. We may take $\delta = \varepsilon / R > 0$.

Step 4 (Chain the containments). Combining Steps 1 and 2:

Step 5 (Conclude via gauge function). For any $\mathbf{e} \in \bar{\boldsymbol{\Omega}}$, we have $\mathbf{A}_{\mathrm{cl}}\mathbf{e} \in (1 - \delta)\bar{\boldsymbol{\Omega}}$, which means $\gamma_{\bar{\boldsymbol{\Omega}}}(\mathbf{A}_{\mathrm{cl}}\mathbf{e}) \le 1 - \delta$. Taking the supremum over all $\mathbf{e} \in \bar{\boldsymbol{\Omega}}$:

Goal. Show that the credible ellipsoid $\mathcal{E}(\mathbf{z}) = \{\mathbf{w} : (\mathbf{w} - \hat{\boldsymbol{\mu}}_w)^\top \hat{\boldsymbol{\Sigma}}_w^{-1}(\mathbf{w} - \hat{\boldsymbol{\mu}}_w) \le \chi^2_{n,1-\alpha}\}$ equals $\hat{\boldsymbol{\mu}}_w \oplus c_{n,\alpha}\hat{\boldsymbol{\Sigma}}_w^{1/2}\mathcal{B}_2^n$.

Step 1 (Existence of the matrix square root). Since $\hat{\boldsymbol{\Sigma}}_w \in \mathbb{S}^n_{++}$ (the GP posterior covariance is positive definite when $\sigma_n^2 > 0$), it admits a unique symmetric positive-definite square root $\hat{\boldsymbol{\Sigma}}_w^{1/2} \in \mathbb{S}^n_{++}$ satisfying $(\hat{\boldsymbol{\Sigma}}_w^{1/2})^2 = \hat{\boldsymbol{\Sigma}}_w$ (Horn & Johnson, Theorem 7.2.6). The inverse $\hat{\boldsymbol{\Sigma}}_w^{-1/2} := (\hat{\boldsymbol{\Sigma}}_w^{1/2})^{-1}$ is also symmetric positive definite.

Step 2 (Apply the whitening transformation). Define the whitened variable $\boldsymbol{\eta} := \hat{\boldsymbol{\Sigma}}_w^{-1/2}(\mathbf{w} - \hat{\boldsymbol{\mu}}_w)$, which is an invertible affine change of variables. Substituting $\mathbf{w} - \hat{\boldsymbol{\mu}}_w = \hat{\boldsymbol{\Sigma}}_w^{1/2}\boldsymbol{\eta}$ into the quadratic form:

Here we used $\hat{\boldsymbol{\Sigma}}_w^{1/2} \hat{\boldsymbol{\Sigma}}_w^{-1} \hat{\boldsymbol{\Sigma}}_w^{1/2} = \hat{\boldsymbol{\Sigma}}_w^{1/2} (\hat{\boldsymbol{\Sigma}}_w^{1/2})^{-1}(\hat{\boldsymbol{\Sigma}}_w^{1/2})^{-1} \hat{\boldsymbol{\Sigma}}_w^{1/2} = \mathbf{I}_n$.

Step 3 (Rewrite the constraint in whitened coordinates). The credible region condition $(\mathbf{w} - \hat{\boldsymbol{\mu}}_w)^\top \hat{\boldsymbol{\Sigma}}_w^{-1}(\mathbf{w} - \hat{\boldsymbol{\mu}}_w) \le \chi^2_{n,1-\alpha}$ becomes:

Step 4 (Invert the transformation). Solving for $\mathbf{w}$ from $\boldsymbol{\eta} = \hat{\boldsymbol{\Sigma}}_w^{-1/2}(\mathbf{w} - \hat{\boldsymbol{\mu}}_w)$:

As $\boldsymbol{\eta}$ ranges over $c_{n,\alpha}\mathcal{B}_2^n$, the vector $\hat{\boldsymbol{\Sigma}}_w^{1/2}\boldsymbol{\eta}$ ranges over $c_{n,\alpha}\hat{\boldsymbol{\Sigma}}_w^{1/2}\mathcal{B}_2^n$ (by linearity of the image). Adding $\hat{\boldsymbol{\mu}}_w$ translates this set:

Goal. Show that $p_{\min}\mathbf{I}_n \preceq \mathbf{P}(\mathbf{x},\mathbf{u}) \preceq p_{\max}\mathbf{I}_n$ for all $(\mathbf{x},\mathbf{u}) \in \mathcal{Z}$, where $\mathbf{P} = c_{n,\alpha}\hat{\boldsymbol{\Sigma}}_w^{1/2}$.

Step 1 (Upper bound on posterior variance). Recall the GP posterior variance for each output component $i$:

Since $\mathbf{G} + \sigma_n^2\mathbf{I}_N \succ \mathbf{0}$ (positive definite) and $\mathbf{k}_*^\top(\mathbf{G} + \sigma_n^2\mathbf{I}_N)^{-1}\mathbf{k}_* \ge 0$ (as $\mathbf{v}^\top \mathbf{A}^{-1}\mathbf{v} \ge 0$ for any PD matrix $\mathbf{A}$), we have:

where the last inequality is Assumption 3 (kernel boundedness).

Step 2 (Upper bound on $\mathbf{P}$). For the full covariance (including LMC cross-terms), the spectral norm satisfies $\|\hat{\boldsymbol{\Sigma}}_w(\mathbf{z})\|_2 \le \bar{k}$ (the prior covariance is the largest possible). Since $\mathbf{P} = c_{n,\alpha}\hat{\boldsymbol{\Sigma}}_w^{1/2}$:

Since $\|\mathbf{P}\|_2 = \lambda_{\max}(\mathbf{P})$, this gives $\mathbf{P}(\mathbf{z}) \preceq p_{\max}\mathbf{I}_n$.

Step 3 (Lower bound via noise floor). We show the posterior variance can never drop below a strictly positive noise floor. The key tool is the Sherman–Morrison formula, which is the rank-1 special case of the Woodbury matrix identity.

Step 3a (Worst-case configuration). We seek a lower bound on $\hat{\sigma}_{w,i}^2(\mathbf{z})$ by maximizing the subtracted term $\mathbf{k}_*^\top(\mathbf{G} + \sigma_n^2\mathbf{I}_N)^{-1}\mathbf{k}_*$ over all possible training configurations. This term is largest when the training points provide maximum information about $f(\mathbf{z})$, which occurs when all $N$ training points coincide with $\mathbf{z}$. In that degenerate limit:

• $\mathbf{k}_* = k(\mathbf{z}, \mathbf{z}^{(j)}) = \bar{k}\,\mathbf{1}_N$  (every training point is at $\mathbf{z}$, so each entry equals $k(\mathbf{z},\mathbf{z}) = \bar{k}$),
• $\mathbf{G} = \bar{k}\,\mathbf{1}_N\mathbf{1}_N^\top$  (all pairwise kernel values equal $\bar{k}$).

Step 3b (Apply Sherman–Morrison). We need $(\bar{k}\,\mathbf{1}_N\mathbf{1}_N^\top + \sigma_n^2\mathbf{I}_N)^{-1}$. Setting $\mathbf{A} = \sigma_n^2\mathbf{I}_N$, $c = \bar{k}$, $\mathbf{u} = \mathbf{v} = \mathbf{1}_N$ in the Sherman–Morrison formula:

Step 3c (Evaluate the quadratic form $\mathbf{k}_*^\top(\cdots)^{-1}\mathbf{k}_*$). With $\mathbf{k}_* = \bar{k}\,\mathbf{1}_N$:

Computing term by term:

• First term: $\displaystyle\frac{\bar{k}^2}{\sigma_n^2}\,\mathbf{1}_N^\top\mathbf{1}_N = \frac{N\bar{k}^2}{\sigma_n^2}$,
• Second term: $\displaystyle\frac{\bar{k}^3}{\sigma_n^2(\sigma_n^2 + N\bar{k})}\,(\mathbf{1}_N^\top\mathbf{1}_N)^2 = \frac{N^2\bar{k}^3}{\sigma_n^2(\sigma_n^2 + N\bar{k})}$.

Step 3d (Posterior variance in the worst case). Subtracting from the prior:

Since the all-points-at-$\mathbf{z}$ case maximizes the subtracted term, for any training configuration:

Step 3e (Effective sample size). Dividing numerator and denominator by $\sigma_n^2$:

Define $N_{\mathrm{eff}} := N\bar{k}/\sigma_n^2$ (an upper bound on $Nk(\mathbf{z},\mathbf{z})/\sigma_n^2$ since $k(\mathbf{z},\mathbf{z}) \le \bar{k}$). Since $k(\mathbf{z},\mathbf{z}) > 0$ for any non-trivial kernel, and $k(\mathbf{z},\mathbf{z}) \ge \sigma_n^2$ in practice (prior signal variance exceeds noise; this holds for all standard kernels such as SE with $\sigma_f^2 \ge \sigma_n^2$), we obtain:

The strict positivity follows from $\sigma_n^2 > 0$. This is the irreducible noise floor: no matter how much data we collect, the posterior variance stays bounded away from zero.

Step 4 (Lower bound on $\mathbf{P}$). Since $\lambda_{\min}(\hat{\boldsymbol{\Sigma}}_w(\mathbf{z})) \ge \sigma_n^2/(1 + N_{\mathrm{eff}})$:

This gives $\mathbf{P}(\mathbf{z}) \succeq p_{\min}\mathbf{I}_n$.

Step 5 (Combine). From Steps 2 and 4, $p_{\min}\mathbf{I}_n \preceq \mathbf{P}(\mathbf{z}) \preceq p_{\max}\mathbf{I}_n$ for all $\mathbf{z} \in \mathcal{Z}$, with $0 < p_{\min} \le p_{\max} < \infty$. $\square$

Goal. Show $\|\mathbf{P}(\mathbf{z}_1) - \mathbf{P}(\mathbf{z}_2)\|_F \le L_P\|\mathbf{z}_1 - \mathbf{z}_2\|$ for all $\mathbf{z}_1, \mathbf{z}_2 \in \mathcal{Z}$.

Step 1 (Lipschitz continuity of the posterior covariance). The GP posterior covariance function is:

Since the kernel $k$ is Lipschitz (Assumption 3 with constant $L_k$), the cross-covariance vectors $\mathbf{k}_*(\mathbf{z})$ are Lipschitz in $\mathbf{z}$. The Gram matrix $(\mathbf{G} + \sigma_n^2\mathbf{I})^{-1}$ is constant (independent of $\mathbf{z}$). By the product rule for Lipschitz functions and the chain rule, $\hat{\boldsymbol{\Sigma}}_w(\cdot)$ is Lipschitz with some constant $L_\Sigma$ depending on $L_k$, $N$ (number of training points), and $\bar{k}$ (kernel bound).

Step 2 (Lipschitz continuity of the matrix square root). A classical result in matrix analysis (Bhatia, 1997) states: on the set $\{\mathbf{A} \in \mathbb{S}^n_{++} : \lambda_{\min}(\mathbf{A}) \ge \underline{\lambda}\}$ for $\underline{\lambda} > 0$, the map $\mathbf{A} \mapsto \mathbf{A}^{1/2}$ is Lipschitz:

This follows from the integral representation $\mathbf{A}^{1/2} - \mathbf{B}^{1/2} = \frac{1}{\pi}\int_0^\infty t^{-1/2}[(t\mathbf{I} + \mathbf{A})^{-1} - (t\mathbf{I} + \mathbf{B})^{-1}]\,dt$ and bounding the resolvent difference.

Step 3 (Verify the eigenvalue floor). From Lemma 3, $\lambda_{\min}(\hat{\boldsymbol{\Sigma}}_w(\mathbf{z})) \ge \sigma_n^2/(1 + N_{\mathrm{eff}}) > 0$ for all $\mathbf{z} \in \mathcal{Z}$. So we can apply Step 2 with $\underline{\lambda} := \sigma_n^2/(1 + N_{\mathrm{eff}})$.

Step 4 (Compose via chain rule). The map $\mathbf{z} \mapsto \mathbf{P}(\mathbf{z}) = c_{n,\alpha}\hat{\boldsymbol{\Sigma}}_w(\mathbf{z})^{1/2}$ is a composition: $\mathbf{z} \xrightarrow{L_\Sigma} \hat{\boldsymbol{\Sigma}}_w(\mathbf{z}) \xrightarrow{1/(2\sqrt{\underline{\lambda}})} \hat{\boldsymbol{\Sigma}}_w(\mathbf{z})^{1/2} \xrightarrow{c_{n,\alpha}} \mathbf{P}(\mathbf{z})$. By the chain rule for Lipschitz functions:

Setting $L_P := c_{n,\alpha} L_\Sigma / (2\sqrt{\underline{\lambda}})$ completes the proof. $\square$

Goal. Show that if the template-coordinate condition $\mathbf{P}'^{-1}\mathbf{A}_{\mathrm{cl}}\mathbf{P}\,\bar{\boldsymbol{\Omega}} \oplus \mathbf{P}'^{-1}\mathbf{P}\,\bar{\mathbf{W}} \subseteq \bar{\boldsymbol{\Omega}}$ holds for all transitions, then $\boldsymbol{\Omega}(\mathbf{x},\mathbf{u}) = \mathbf{P}(\mathbf{x},\mathbf{u})\bar{\boldsymbol{\Omega}}$ is locally RPI.

Step 1 (Express error in template coordinates). At time $k$, suppose $\mathbf{e}_k \in \boldsymbol{\Omega}(\mathbf{x}_k,\mathbf{u}_k) = \mathbf{P}_k\bar{\boldsymbol{\Omega}}$, where $\mathbf{P}_k := \mathbf{P}(\mathbf{x}_k,\mathbf{u}_k)$. By definition, there exists $\boldsymbol{\xi} \in \bar{\boldsymbol{\Omega}}$ such that:

Step 2 (Express disturbance in template coordinates). Similarly, $\mathbf{w}_k \in \mathbb{W}(\mathbf{x}_k,\mathbf{u}_k) = \mathbf{P}_k\bar{\mathbf{W}}$, so there exists $\boldsymbol{\eta} \in \bar{\mathbf{W}}$ with:

Step 3 (Propagate the error dynamics). The error dynamics gives:

Step 4 (Transform to the successor template coordinates). We want to show $\mathbf{e}_{k+1} \in \boldsymbol{\Omega}(\mathbf{x}_{k+1},\mathbf{u}_{k+1}) = \mathbf{P}_{k+1}\bar{\boldsymbol{\Omega}}$, where $\mathbf{P}_{k+1} := \mathbf{P}(\mathbf{x}_{k+1},\mathbf{u}_{k+1})$. Define the transformed successor error:

Note that $\mathbf{e}_{k+1} \in \mathbf{P}_{k+1}\bar{\boldsymbol{\Omega}}$ if and only if $\tilde{\mathbf{e}}_{k+1} \in \bar{\boldsymbol{\Omega}}$.

Step 5 (Decompose into Minkowski sum structure). Using linearity of $\mathbf{P}_{k+1}^{-1}$:

As $\boldsymbol{\xi}$ ranges over $\bar{\boldsymbol{\Omega}}$ and $\boldsymbol{\eta}$ ranges over $\bar{\mathbf{W}}$, the set of all possible $\tilde{\mathbf{e}}_{k+1}$ is exactly:

Step 6 (Apply the hypothesis). The theorem's condition states exactly that this Minkowski sum is contained in $\bar{\boldsymbol{\Omega}}$:

Therefore $\tilde{\mathbf{e}}_{k+1} \in \bar{\boldsymbol{\Omega}}$, and hence:

Step 7 (Conclude). Since this holds for arbitrary $\boldsymbol{\xi} \in \bar{\boldsymbol{\Omega}}$, $\boldsymbol{\eta} \in \bar{\mathbf{W}}$, and arbitrary transitions $(\mathbf{x}_k,\mathbf{u}_k) \to (\mathbf{x}_{k+1},\mathbf{u}_{k+1})$, we have shown: $\mathbf{e}_k \in \boldsymbol{\Omega}(\mathbf{x}_k,\mathbf{u}_k)$ implies $\mathbf{e}_{k+1} \in \boldsymbol{\Omega}(\mathbf{x}_{k+1},\mathbf{u}_{k+1})$ for all admissible disturbances. This is exactly the definition of local RPI. $\square$

Goal. Derive the LMI from the invariance condition using the S-procedure.

Step 1 (Restate the invariance condition). With templates $\bar{\boldsymbol{\Omega}} = r\mathcal{B}_2^n$ and $\bar{\mathbf{W}} = \mathcal{B}_2^n$, the condition from Theorem 1 requires: for all $\boldsymbol{\xi}$ with $\|\boldsymbol{\xi}\|_2 \le r$ and $\boldsymbol{\eta}$ with $\|\boldsymbol{\eta}\|_2 \le 1$, we need $\|\mathbf{P}'^{-1}\mathbf{A}_{\mathrm{cl}}\mathbf{P}\boldsymbol{\xi} + \mathbf{P}'^{-1}\mathbf{P}\boldsymbol{\eta}\|_2 \le r$. Substituting $\boldsymbol{\xi} = r\boldsymbol{\xi}'$ with $\|\boldsymbol{\xi}'\|_2 \le 1$ and dividing by $r$, this becomes $\|\mathbf{M}\boldsymbol{\xi}' + \mathbf{N}\boldsymbol{\eta}\|_2 \le 1$, where $\mathbf{M} := \mathbf{P}'^{-1}\mathbf{A}_{\mathrm{cl}}\mathbf{P}$ and $\mathbf{N} := \tfrac{1}{r}\mathbf{P}'^{-1}\mathbf{P}$.

Step 2 (Formulate as quadratic functions). Define the stacked vector $\mathbf{z} := [\boldsymbol{\xi}^\top, \boldsymbol{\eta}^\top]^\top \in \mathbb{R}^{2n}$ and three quadratic functions:

The invariance condition is: $f_1(\mathbf{z}) \ge 0$ and $f_2(\mathbf{z}) \ge 0$ $\Rightarrow$ $f_0(\mathbf{z}) \ge 0$.

Step 3 (Apply the multi-constraint S-procedure). The S-procedure provides a sufficient condition: if there exist $\lambda_1,\lambda_2\ge 0$ such that

then the implication $f_1\ge0,\;f_2\ge0\Rightarrow f_0\ge0$ holds. The constant term gives the additional constraint $\lambda_1+\lambda_2\le1$.

Step 4 (Expand $f_0$ in quadratic form). First expand the squared norm:

Step 5 (Write the quadratic condition). With $\mathbf{z}:=[\boldsymbol{\xi}^\top,\boldsymbol{\eta}^\top]^\top$, the inequality $f_0(\mathbf{z})-\lambda_1 f_1(\mathbf{z})-\lambda_2 f_2(\mathbf{z})\ge0$ for all $\mathbf{z}$ is equivalent to the quadratic matrix inequality

Step 6 (Obtain the LMI). This is the stated LMI. The condition $\lambda_1+\lambda_2\le1$ comes from the constant term in the S-procedure inequality.

Step 7 (Conclude). If this LMI is feasible for some $\lambda_1,\lambda_2\ge0$ with $\lambda_1+\lambda_2\le1$, then the S-procedure implies $\|\mathbf{M}\boldsymbol{\xi}+\mathbf{N}\boldsymbol{\eta}\|_2\le1$ whenever $\|\boldsymbol{\xi}\|_2\le1$ and $\|\boldsymbol{\eta}\|_2\le1$. By Theorem 1, the tube field is locally RPI. $\square$

Goal. Bound $\lambda_{\max}(\mathbf{P}(\mathbf{z}))$ from above and $\lambda_{\min}(\mathbf{P}(\mathbf{z}))$ from below for all $\mathbf{z} \in \mathcal{R}_i$.

Step 1 (Lipschitz bound on matrix perturbation). By Assumption 2, the field $\mathbf{P}$ is Lipschitz with constant $L_P$. For any $\mathbf{z} \in \mathcal{R}_i$, the node $\mathbf{z}_i$ satisfies $\|\mathbf{z} - \mathbf{z}_i\|_2 \le \mathrm{rad}(\mathcal{R}_i)$, so:

Step 2 (Write as symmetric perturbation). Define the perturbation $\mathbf{E} := \mathbf{P}(\mathbf{z}) - \mathbf{P}_i$. Since both $\mathbf{P}(\mathbf{z})$ and $\mathbf{P}_i$ are symmetric (they are in $\mathbb{S}^n_{++}$), $\mathbf{E} \in \mathbb{S}^n$ with $\|\mathbf{E}\|_2 \le \delta_i$. We can write $\mathbf{P}(\mathbf{z}) = \mathbf{P}_i + \mathbf{E}$.

Step 3 (Apply Weyl's inequality for $\lambda_{\max}$). Weyl's eigenvalue perturbation inequality states: for symmetric $\mathbf{A}, \mathbf{B} \in \mathbb{S}^n$,

Applying with $\mathbf{A} = \mathbf{P}_i$ and $\mathbf{B} = \mathbf{E}$ for $k = n$ (largest eigenvalue):

Therefore $\lambda_{\max}(\mathbf{P}(\mathbf{z})) \le \lambda_{\max}(\mathbf{P}_i) + \delta_i = p_i^+$.

Step 4 (Apply Weyl's inequality for $\lambda_{\min}$). Similarly, for $k = 1$ (smallest eigenvalue):

The lower bound gives $\lambda_{\min}(\mathbf{P}(\mathbf{z})) \ge \lambda_{\min}(\mathbf{P}_i) - \delta_i = p_i^-$.

Step 5 (Conclude). For all $\mathbf{z} \in \mathcal{R}_i$:

Under Assumption 5 ($\delta_i < \lambda_{\min}(\mathbf{P}_i)$), we have $p_i^- > 0$, confirming $\mathbf{P}(\mathbf{z}) \succ \mathbf{0}$. $\square$

Goal. Bound $\|\mathbf{M}\|_2$ and $\|\mathbf{N}\|_2$ using only node-computable quantities $p_i^+, p_j^-$.

Step 1 (Upper bound on $\|\mathbf{P}(\mathbf{z})\|_2$). For $\mathbf{z} \in \mathcal{R}_i$, since $\mathbf{P}(\mathbf{z}) \in \mathbb{S}^n_{++}$, its spectral norm equals its largest eigenvalue:

Step 2 (Upper bound on $\|\mathbf{P}(\mathbf{z}')^{-1}\|_2$). For $\mathbf{z}' \in \mathcal{R}_j$, Lemma 6 gives $\lambda_{\min}(\mathbf{P}(\mathbf{z}')) \ge p_j^-$. For a positive definite matrix, the spectral norm of its inverse is the reciprocal of its smallest eigenvalue:

This is well-defined since $p_j^- > 0$ by Assumption 5.

Step 3 (Bound $\|\mathbf{M}\|_2$ via submultiplicativity). Recall $\mathbf{M} = \mathbf{P}(\mathbf{z}')^{-1}\mathbf{A}_{\mathrm{cl}}\mathbf{P}(\mathbf{z})$. The spectral norm is submultiplicative ($\|\mathbf{A}\mathbf{B}\|_2 \le \|\mathbf{A}\|_2 \|\mathbf{B}\|_2$), so:

Step 4 (Bound $\|\mathbf{N}\|_2$ similarly). Recall $\mathbf{N} = \tfrac{1}{r}\mathbf{P}(\mathbf{z}')^{-1}\mathbf{P}(\mathbf{z})$:

Step 5 (Conclude). Both bounds depend only on the spectral bound parameters $p_i^+$ and $p_j^-$ (and the template inflation factor $r$), which are computable from the node values $\lambda_{\max}(\mathbf{P}_i), \lambda_{\min}(\mathbf{P}_j)$ and the Lipschitz radii $\delta_i, \delta_j$. No evaluation of $\mathbf{P}(\cdot)$ at interior points of $\mathcal{R}_i$ or $\mathcal{R}_j$ is needed. $\square$

Goal. Show that the spectral edge condition implies the invariance condition from Theorem 1 for all continuous transitions, reducing infinite verification to a finite graph check.

Step 1 (Reduce to the norm condition). With templates $\bar{\boldsymbol{\Omega}} = r\mathcal{B}_2^n$ and $\bar{\mathbf{W}} = \mathcal{B}_2^n$, by Theorem 2 it suffices to show that for every transition $\mathbf{z} = (\mathbf{x},\mathbf{u}) \in \mathcal{R}_i \to \mathbf{z}' = (\mathbf{x}',\mathbf{u}') \in \mathcal{R}_j$ with $(i,j) \in \mathcal{A}$:

where $\mathbf{M} := \mathbf{P}(\mathbf{z}')^{-1}\mathbf{A}_{\mathrm{cl}}\mathbf{P}(\mathbf{z})$ and $\mathbf{N} := \tfrac{1}{r}\mathbf{P}(\mathbf{z}')^{-1}\mathbf{P}(\mathbf{z})$.

Step 2 (Apply triangle inequality). For any $\boldsymbol{\xi}', \boldsymbol{\eta}$ with $\|\boldsymbol{\xi}'\|_2 \le 1$ and $\|\boldsymbol{\eta}\|_2 \le 1$:

The second inequality uses the definition of the operator norm: $\|\mathbf{A}\mathbf{v}\|_2 \le \|\mathbf{A}\|_2\|\mathbf{v}\|_2$.

Step 3 (Insert spectral bounds from Lemma 7). For $\mathbf{z} \in \mathcal{R}_i$ and $\mathbf{z}' \in \mathcal{R}_j$, Lemma 7 provides:

Adding these:

Step 4 (Apply the arc condition). The theorem's hypothesis states that for every $(i,j) \in \mathcal{A}$:

Step 5 (Chain the bounds). Combining Steps 2-4:

This holds for all $\boldsymbol{\xi}', \boldsymbol{\eta} \in \mathcal{B}_2^n$ and for all continuous $\mathbf{z} \in \mathcal{R}_i$, $\mathbf{z}' \in \mathcal{R}_j$ (not just at the nodes).

Step 6 (Completeness of the graph). Assumption 4 guarantees that for every feasible transition $(\mathbf{x},\mathbf{u}) \to (\mathbf{x}',\mathbf{u}')$, there exists an arc $(i,j) \in \mathcal{A}$ covering it. Therefore the norm condition is satisfied for all transitions in $\mathcal{Z}$, not just those between specific nodes.

Conclusion. By Theorem 1, satisfaction of the norm condition for all transitions implies local RPI of $\boldsymbol{\Omega}(\mathbf{z}) = \mathbf{P}(\mathbf{z})r\mathcal{B}_2^n$. The infinite verification over a continuous domain has been reduced to checking the scalar inequality $\frac{p_i^+}{p_j^-}(\gamma_{\mathrm{cl}} + 1/r) \le 1$ at each of the finitely many arcs $(i,j) \in \mathcal{A}$. $\square$

Goal. Show that the scalar-bound LMI implies the full LMI of Theorem 2 for all $\mathbf{M},\mathbf{N}$ satisfying the spectral bounds.

From Lemma 7, $\|\mathbf{M}\|_2 \leq \bar{M}_{ij}$ and $\|\mathbf{N}\|_2 \leq \bar{N}_{ij}$. Therefore, for any vectors $\boldsymbol{\xi},\boldsymbol{\eta}$,

The scalar-bound LMI is exactly the quadratic certificate that

for all $\boldsymbol{\xi},\boldsymbol{\eta}$, with $\lambda_1,\lambda_2\ge0$ and $\lambda_1+\lambda_2\le1$. Hence the full Theorem 2 LMI holds for all matrices satisfying the norm bounds.

For scalars, feasibility of this LMI with $\lambda_1,\lambda_2\ge0$ and $\lambda_1+\lambda_2\le1$ is equivalent to $\bar{M}_{ij}+\bar{N}_{ij}\le1$. Thus the scalar-bound LMI recovers the same arc-wise spectral condition. The full LMI can still be less conservative when evaluated with the actual matrices $\mathbf{M}$ and $\mathbf{N}$ rather than only their scalar norm bounds. $\square$

Step 1. For a constant field, $\delta_i = 0$ for all $i$, so $p_i^+ = p_i^- = p$ and $p_i^+/p_j^- = 1$ for all $(i,j) \in \mathcal{A}$.

Step 2. The spectral condition evaluates to:

Step 3. Since this holds for every arc, $p\,\mathbf{I}_n \in \mathscr{A}$. $\square$

Goal. Show that if $\boldsymbol{\Sigma}_1(\mathbf{z}) \preceq \boldsymbol{\Sigma}_2(\mathbf{z})$ pointwise and $\mathbf{P}_i = c\,\boldsymbol{\Sigma}_i^{1/2}$, then (1) $\boldsymbol{\Omega}_1 := \mathbf{P}_1\bar{\boldsymbol{\Omega}} \subseteq \mathbf{P}_2\bar{\boldsymbol{\Omega}} =: \boldsymbol{\Omega}_2$ pointwise, and (2) both are locally RPI.

Part 1: Set containment $\boldsymbol{\Sigma}_1^{1/2}\mathcal{B}_2^n \subseteq \boldsymbol{\Sigma}_2^{1/2}\mathcal{B}_2^n$.

Since $\mathbf{P}_i = c\,\boldsymbol{\Sigma}_i^{1/2}$ and the template $\bar{\boldsymbol{\Omega}} = r\mathcal{B}_2^n$, we have $\boldsymbol{\Omega}_i = cr\,\boldsymbol{\Sigma}_i^{1/2}\mathcal{B}_2^n$. The positive scalars $c,r$ factor out identically on both sides, so it suffices to prove $\boldsymbol{\Sigma}_1^{1/2}\mathcal{B}_2^n \subseteq \boldsymbol{\Sigma}_2^{1/2}\mathcal{B}_2^n$.

Step 1a (Pick arbitrary element). Let $\mathbf{e} \in \boldsymbol{\Sigma}_1^{1/2}\mathcal{B}_2^n$. Then there exists $\boldsymbol{\xi} \in \mathcal{B}_2^n$ ($\|\boldsymbol{\xi}\|_2 \le 1$) such that $\mathbf{e} = \boldsymbol{\Sigma}_1^{1/2}\boldsymbol{\xi}$.

Step 1b (Express in $\boldsymbol{\Sigma}_2^{1/2}$-coordinates). Define $\boldsymbol{\zeta} := \boldsymbol{\Sigma}_2^{-1/2}\mathbf{e} = \boldsymbol{\Sigma}_2^{-1/2}\boldsymbol{\Sigma}_1^{1/2}\boldsymbol{\xi}$. We need to show $\|\boldsymbol{\zeta}\|_2 \le 1$, which would mean $\mathbf{e} = \boldsymbol{\Sigma}_2^{1/2}\boldsymbol{\zeta} \in \boldsymbol{\Sigma}_2^{1/2}\mathcal{B}_2^n$.

Step 1c (Form $\mathbf{C}\mathbf{C}^\top$ from the covariance ordering). Define $\mathbf{C} := \boldsymbol{\Sigma}_2^{-1/2}\boldsymbol{\Sigma}_1^{1/2}$. Because $\boldsymbol{\Sigma}_1^{1/2}$ is symmetric (it is the unique SPD square root), we can compute:

This is a congruence of $\boldsymbol{\Sigma}_1$ by the invertible matrix $\boldsymbol{\Sigma}_2^{-1/2}$. Congruences preserve the Löwner ordering: from $\boldsymbol{\Sigma}_1 \preceq \boldsymbol{\Sigma}_2$,

Step 1d (Bound the spectral norm of $\mathbf{C}$). The matrix $\mathbf{C}\mathbf{C}^\top$ is symmetric positive semidefinite with all eigenvalues $\le 1$. The squared spectral norm of $\mathbf{C}$ equals the largest eigenvalue of $\mathbf{C}\mathbf{C}^\top$:

This step is correct precisely because $\mathbf{C}\mathbf{C}^\top$ is symmetric — for a symmetric matrix, the spectral norm equals the spectral radius. (For a generic non-symmetric matrix, eigenvalues $\le 1$ would not imply $\|\cdot\|_2 \le 1$.)

Step 1e (Conclude containment).

Therefore $\boldsymbol{\zeta} \in \mathcal{B}_2^n$ and $\mathbf{e} = \boldsymbol{\Sigma}_2^{1/2}\boldsymbol{\zeta} \in \boldsymbol{\Sigma}_2^{1/2}\mathcal{B}_2^n$. Scaling by $cr$ gives $\mathbf{P}_1\bar{\boldsymbol{\Omega}} \subseteq \mathbf{P}_2\bar{\boldsymbol{\Omega}}$.

Part 2: Both fields are RPI. Both $\mathbf{P}_1$ and $\mathbf{P}_2$ satisfy the spectral invariance condition by assumption. Theorem 3 then directly implies both $\boldsymbol{\Omega}_1$ and $\boldsymbol{\Omega}_2$ are locally RPI. The containment from Part 1 means $\boldsymbol{\Omega}_1$ provides strictly tighter uncertainty tubes. $\square$

Part 2: Anisotropy field shrinkage $\mathbf{P}^{(q+1)} \preceq \mathbf{P}^{(q)}$.

Step 2a (Recall the definition). The anisotropy field is $\mathbf{P}^{(q)}(\mathbf{z}) := c_{n,\alpha}[\hat{\boldsymbol{\Sigma}}_w^{(q)}(\mathbf{z})]^{1/2}$, where $c_{n,\alpha} > 0$ is a scalar confidence scaling factor.

Step 2b (Invoke the Löwner-Heinz theorem). The matrix square root $t \mapsto t^{1/2}$ is operator monotone on $\mathbb{S}^n_+$ (Löwner-Heinz theorem with exponent $r = 1/2$). This means:

Step 2c (Apply to the posterior covariance). Part 1 established $\hat{\boldsymbol{\Sigma}}_w^{(q+1)}(\mathbf{z}) \preceq \hat{\boldsymbol{\Sigma}}_w^{(q)}(\mathbf{z})$. Applying operator monotonicity of the square root:

Step 2d (Scale by the confidence factor). Multiplying both sides by $c_{n,\alpha} > 0$ preserves the ordering (positive scalar multiplication is order-preserving):

Part 3: Tube contraction $\boldsymbol{\Omega}^{(q+1)} \subseteq \boldsymbol{\Omega}^{(q)}$.

Step 3a (Invoke Proposition 2). Part 1 established the covariance ordering $\hat{\boldsymbol{\Sigma}}_w^{(q+1)}(\mathbf{z}) \preceq \hat{\boldsymbol{\Sigma}}_w^{(q)}(\mathbf{z})$ for all $\mathbf{z} \in \mathcal{Z}$. Since $\mathbf{P}^{(q)} = c_{n,\alpha}[\hat{\boldsymbol{\Sigma}}_w^{(q)}]^{1/2}$, Proposition 2 (with $\boldsymbol{\Sigma}_i = \hat{\boldsymbol{\Sigma}}_w^{(i)}$ and $c = c_{n,\alpha}$) gives set containment:

for all $\mathbf{z} \in \mathcal{Z}$.

Step 3b (Geometric interpretation). Each ellipsoidal cross-section $\boldsymbol{\Omega}^{(q+1)}(\mathbf{z})$ is nested inside $\boldsymbol{\Omega}^{(q)}(\mathbf{z})$, with the nesting preserving the anisotropic shape. The semi-axes of the ellipsoid shrink monotonically in every direction as data accumulate, with directions of high data density shrinking fastest. $\square$

Goal. Show $\hat{\boldsymbol{\Sigma}}_w^{(q+1)}(\mathbf{z}_*)\preceq\hat{\boldsymbol{\Sigma}}_w^{(q)}(\mathbf{z}_*)$ for all $\mathbf{z}_*\in\mathcal{Z}$ using Schur complement properties.

Step 1 (GP posterior as Schur complement). The GP posterior covariance at a test point $\mathbf{z}_*$ conditioned on data $\mathcal{D}^{(q)}$ is:

This is precisely the Schur complement of the $(\mathcal{D},\mathcal{D})$ block in the joint covariance matrix. Consider the joint distribution of $[\mathbf{w}(\mathbf{z}_*), \mathbf{y}_{\mathcal{D}^{(q)}}]$ where $\mathbf{y} = \mathbf{w} + \boldsymbol{\epsilon}$ ($\boldsymbol{\epsilon} \sim \mathcal{N}(\mathbf{0}, \sigma_n^2\mathbf{I})$). The joint covariance is:

Then $\hat{\boldsymbol{\Sigma}}_w^{(q)}(\mathbf{z}_*) = \mathbf{G}^{(q)} / (\boldsymbol{\Sigma}_{\mathcal{D}\mathcal{D}} + \sigma_n^2\mathbf{I})$ (Schur complement notation).

Step 2 (Augment the conditioning set). At epoch $q{+}1$, one new data point is added: $\mathcal{D}^{(q+1)} = \mathcal{D}^{(q)} \cup \{(\mathbf{z}^{\mathrm{new}}, \mathbf{y}^{\mathrm{new}})\}$. The joint covariance becomes:

The posterior is now $\hat{\boldsymbol{\Sigma}}_w^{(q+1)}(\mathbf{z}_*) = \mathbf{G}^{(q+1)} / (\text{lower-right } (nN_q + n) \times (nN_q + n) \text{ block})$.

Step 3 (Apply the Schur complement monotonicity lemma). There is a standard result from matrix analysis:

In words: the Schur complement of a larger principal submatrix is always $\preceq$ the Schur complement of a smaller one. This is because conditioning on more variables can only reduce (or maintain) the conditional variance.

Step 4 (Identify the blocks). In our setting: $\mathbf{A} = \boldsymbol{\Sigma}_{**}$ (test point block), $\mathbf{D} = \boldsymbol{\Sigma}_{\mathcal{D}\mathcal{D}} + \sigma_n^2\mathbf{I}$ (old data block), $\mathbf{F} = \boldsymbol{\Sigma}_{\mathrm{new,new}} + \sigma_n^2\mathbf{I}$ (new data block). Then:

• $\mathbf{G}^{(q+1)} / \begin{bmatrix}\mathbf{D} & \mathbf{E} \\ \mathbf{E}^\top & \mathbf{F}\end{bmatrix} = \hat{\boldsymbol{\Sigma}}_w^{(q+1)}(\mathbf{z}_*)$ (posterior with all data),
• $\mathbf{G}^{(q)} / \mathbf{D} = \hat{\boldsymbol{\Sigma}}_w^{(q)}(\mathbf{z}_*)$ (posterior with old data only).

Step 5 (Conclude). By the Schur complement monotonicity lemma:

This is the most conceptually clean proof: it uses only the fact that conditioning on more data (enlarging the Schur complement's denominator block) can only reduce uncertainty. $\square$

Goal. Show $\hat{\boldsymbol{\Sigma}}_w^{(q+1)}(\mathbf{z}_*)\preceq\hat{\boldsymbol{\Sigma}}_w^{(q)}(\mathbf{z}_*)$ for all $\mathbf{z}_*\in\mathcal{Z}$ using information (precision) matrices.

Step 1 (Define the information matrix). The information matrix (precision matrix) at $\mathbf{z}_*$ given data $\mathcal{D}^{(q)}$ is:

Higher information (larger $\boldsymbol{\Lambda}$ in the Löwner sense) corresponds to lower uncertainty (smaller $\hat{\boldsymbol{\Sigma}}_w$).

Step 2 (Information update formula). When a new observation $(\mathbf{z}^{\mathrm{new}}, \mathbf{y}^{\mathrm{new}})$ is incorporated, the information matrix updates as:

where $\mathbf{H} \in \mathbb{R}^{n \times n}$ is the "observation model" matrix relating the test point to the new observation (derived from the GP cross-covariance structure), and $\boldsymbol{\Gamma} \succ \mathbf{0}$ is the innovation covariance. This is the multi-output generalization of the scalar information filter update.

Step 3 (Show the update is PSD). The update term $\mathbf{H}^\top\boldsymbol{\Gamma}^{-1}\mathbf{H}$ is positive semidefinite. For any $\mathbf{v} \in \mathbb{R}^n$:

since $\boldsymbol{\Gamma}^{-1} \succ \mathbf{0}$ and $\mathbf{w}^\top\boldsymbol{\Gamma}^{-1}\mathbf{w} \ge 0$ for all $\mathbf{w}$.

Step 4 (Conclude information growth). Therefore:

Information can only grow (or stay the same) as data are added.

Step 5 (Invert using order reversal). On $\mathbb{S}^n_{++}$, the map $\mathbf{X} \mapsto \mathbf{X}^{-1}$ reverses the Löwner order:

Proof of reversal: If $\mathbf{A} \succeq \mathbf{B} \succ \mathbf{0}$, then for any $\mathbf{v} \ne \mathbf{0}$, set $\mathbf{u} = \mathbf{B}^{-1/2}\mathbf{v}$. We have $\mathbf{u}^\top\mathbf{B}^{1/2}\mathbf{A}^{-1}\mathbf{B}^{1/2}\mathbf{u} \le \mathbf{u}^\top\mathbf{u}$ (since $\mathbf{A}^{-1} \preceq \mathbf{B}^{-1}$ is equivalent to $\mathbf{B}^{1/2}\mathbf{A}^{-1}\mathbf{B}^{1/2} \preceq \mathbf{I}$, which follows from $\mathbf{B}^{-1/2}\mathbf{A}\mathbf{B}^{-1/2} \succeq \mathbf{I}$).

Step 6 (Conclude). Applying order reversal to Step 4:

This route is perhaps the most intuitive: data add information ($\boldsymbol{\Lambda}$ grows), and inversion converts information growth into uncertainty reduction. $\square$

This is a self-contained, step-by-step derivation of posterior covariance monotonicity via explicit block matrix inversion. It uses no abbreviations and shows every intermediate step.

Setup and Notation

Consider a multi-output GP with $n$ outputs under the Linear Model of Coregionalization (LMC). At epoch $q$, the dataset is $\mathcal{D}^{(q)}=\{(\mathbf{z}^{(j)},\mathbf{w}^{(j)})\}_{j=1}^{N_q}$. The GP posterior covariance at a test point $\mathbf{z}_*\in\mathcal{Z}$ is

where $\boldsymbol{\Sigma}_{**}:=K_{\mathrm{LMC}}(\mathbf{z}_*,\mathbf{z}_*)\in\mathbb{R}^{n\times n}$ is the prior covariance, $\boldsymbol{\Sigma}_{*\mathcal{D}^{(q)}}\in\mathbb{R}^{n\times nN_q}$ is the cross-covariance, $\boldsymbol{\Sigma}_{\mathcal{D}^{(q)}\mathcal{D}^{(q)}}\in\mathbb{R}^{nN_q\times nN_q}$ is the training kernel matrix, and $\sigma_n^2>0$ is the observation noise.

At epoch $q{+}1$, one new data point $(\mathbf{z}^{\mathrm{new}},\mathbf{w}^{\mathrm{new}})$ is added: $\mathcal{D}^{(q+1)}=\mathcal{D}^{(q)}\cup\{(\mathbf{z}^{\mathrm{new}},\mathbf{w}^{\mathrm{new}})\}$.

Goal: Prove $\hat{\boldsymbol{\Sigma}}_w^{(q+1)}(\mathbf{z}_*)\preceq\hat{\boldsymbol{\Sigma}}_w^{(q)}(\mathbf{z}_*)$ for all $\mathbf{z}_*\in\mathcal{Z}$.

Step 1: Define Shorthand

Fix a test point $\mathbf{z}_*$ and define:

Note $\mathbf{M}_1\succ\mathbf{0}$ (since the kernel matrix is PSD and $\sigma_n^2>0$) and $\mathbf{d}\succ\mathbf{0}$.

Step 2: Explained Variance at Epoch $q$

Define the explained variance:

The goal $\hat{\boldsymbol{\Sigma}}_w^{(q+1)}\preceq\hat{\boldsymbol{\Sigma}}_w^{(q)}$ is equivalent to $\boldsymbol{\Phi}^{(q+1)}\succeq\boldsymbol{\Phi}^{(q)}$ (since $\boldsymbol{\Sigma}_{**}$ is the same at both epochs).

Step 3: Augmented System at Epoch $q{+}1$

At epoch $q{+}1$, the augmented matrices are:

The explained variance at $q{+}1$:

Step 4: Block Inversion of $\mathbf{M}_2$

Using the standard $2\times 2$ block inversion formula (Horn & Johnson, Sec. 0.7.3). Define the Schur complement:

Claim: $\boldsymbol{\Delta}\succ\mathbf{0}$. Since $\mathbf{M}_2\succ\mathbf{0}$ and $\mathbf{M}_1\succ\mathbf{0}$, the Schur complement characterization of positive definiteness gives $\boldsymbol{\Delta}\succ\mathbf{0}$.

Interpretation: Expanding, $\boldsymbol{\Delta}=\hat{\boldsymbol{\Sigma}}_w^{(q)}(\mathbf{z}^{\mathrm{new}})+\sigma_n^2\mathbf{I}_n$ (the posterior covariance at the new point, plus noise).

The block inverse is:

Step 5: Expanding $\boldsymbol{\Phi}^{(q+1)}$ into Four Terms

Performing the block multiplication $\boldsymbol{\Phi}^{(q+1)}=T_1+T_2+T_3+T_4$:

Term $T_1$ (top-left block):

Term $T_2$ (top-right $\times$ bottom):

Term $T_3$ (bottom-left $\times$ top) = $T_2^\top$:

Term $T_4$ (bottom-right):

Step 6: Define Auxiliary Quantity and Factor

Define the predicted cross-covariance:

This is the part of the $(\mathbf{z}_*,\mathbf{z}^{\mathrm{new}})$ correlation already explained by old data.

Rewriting the four terms using $\mathbf{Q}$:

Define the residual cross-covariance (the "new information"):

Factorization. The last four terms factor as $\mathbf{R}\boldsymbol{\Delta}^{-1}\mathbf{R}^\top$. Verification by expansion:

This matches the remaining terms exactly. Therefore:

Step 7: Positive Semidefiniteness

Lemma. For any $\mathbf{R}\in\mathbb{R}^{n\times n}$ and $\boldsymbol{\Delta}\succ\mathbf{0}$, the product $\mathbf{R}\boldsymbol{\Delta}^{-1}\mathbf{R}^\top\succeq\mathbf{0}$.

Proof. Since $\boldsymbol{\Delta}\succ\mathbf{0}$, we have $\boldsymbol{\Delta}^{-1}\succ\mathbf{0}$. For any $\mathbf{v}\in\mathbb{R}^n$, let $\mathbf{w}:=\mathbf{R}^\top\mathbf{v}$. Then:

since $\boldsymbol{\Delta}^{-1}\succ\mathbf{0}$. $\square$

Step 8: Conclusion

Combining Steps 6-7:

Since $\boldsymbol{\Phi}^{(q)}=\boldsymbol{\Sigma}_{**}-\hat{\boldsymbol{\Sigma}}_w^{(q)}$ with the same $\boldsymbol{\Sigma}_{**}$:

GP Interpretation

The residual $\mathbf{R}$ and Schur complement $\boldsymbol{\Delta}$ have natural GP interpretations:

• $\mathbf{R}=\mathrm{Cov}^{(q)}(\mathbf{w}(\mathbf{z}_*),\mathbf{w}(\mathbf{z}^{\mathrm{new}}))$ - the posterior cross-covariance between the test point and the new point.
• $\boldsymbol{\Delta}=\mathrm{Var}^{(q)}(\mathbf{w}(\mathbf{z}^{\mathrm{new}}))+\sigma_n^2\mathbf{I}_n$ - the posterior variance at the new point, plus noise.

So the increment formula reads:

Scalar Sanity Check

For $n=1$ (single output), all "matrices" become scalars: $\mathbf{R}\to r$, $\boldsymbol{\Delta}\to\delta>0$. The formula becomes $\Phi^{(q+1)}-\Phi^{(q)}=r^2/\delta\ge 0$, recovering the standard scalar GP posterior variance update. $\square$

Goal. Show that the uniform condition $\frac{p_{\max}^{(q)}}{p_{\min}^{(q)}}(\|\mathbf{A}_{\mathrm{cl}}\|_2 + 1/r) \le 1$ implies the arc-wise condition for every $(i,j) \in \mathcal{A}$.

Step 1 (Recall definitions). The global spectral bounds are:

The local spectral bounds from Definition 7 are $p_i^+ = \lambda_{\max}(\mathbf{P}_i) + \delta_i$ and $p_j^- = \lambda_{\min}(\mathbf{P}_j) - \delta_j$.

Step 2 (Bound $p_i^+$ from above). For any node $i$, by Lemma 6, $\lambda_{\max}(\mathbf{P}(\mathbf{z})) \le p_i^+$ for all $\mathbf{z} \in \mathcal{R}_i$. Since $p_{\max}^{(q)}$ is the supremum over all $\mathbf{z} \in \mathcal{Z} = \bigcup_i \mathcal{R}_i$:

(In fact $p_i^+$ could be larger than $\max_{\mathbf{z} \in \mathcal{R}_i} \lambda_{\max}(\mathbf{P}(\mathbf{z}))$ due to the Lipschitz over-approximation, but it is always bounded by the global maximum.)

Step 3 (Bound $p_j^-$ from below). Similarly, $\lambda_{\min}(\mathbf{P}(\mathbf{z})) \ge p_j^-$ for all $\mathbf{z} \in \mathcal{R}_j$. Since $p_{\min}^{(q)}$ is the infimum:

Step 4 (Form the ratio bound). For any arc $(i,j) \in \mathcal{A}$:

The last inequality is the uniform condition assumed in the proposition.

Step 5 (Conclude). Since this holds for every $(i,j) \in \mathcal{A}$, the arc-wise spectral condition of Theorem 3 is satisfied. Note that the uniform condition is sufficient but not necessary: individual arcs may satisfy $\frac{p_i^+}{p_j^-}(\|\mathbf{A}_{\mathrm{cl}}\|_2 + 1/r) \le 1$ even when the global ratio $p_{\max}^{(q)}/p_{\min}^{(q)}$ violates the uniform bound. $\square$