Prove that the following matrix is positive definite

Question

We define $K_{\mathbf{a}, \mathbf{b}}$ as the $n \times m$ matrix whose $ij^{th}$ entry is $\kappa(a_{i}, b_{j})$
Where, $\kappa$ is a (positive definite) kernel function.
Here, $\mathbf{a}_{i}, \mathbf{b}_{j} \in \mathbb{R}^{D} \hspace{10pt} \forall \hspace{3pt}0 \leq i < n, 0 \leq j < m$

Here $D \neq n, m$ in general

Show that $K_{\mathbf{a},\mathbf{a}} - K_{\mathbf{a},\mathbf{b}}K_{\mathbf{b},\mathbf{b}}^{-1}K_{\mathbf{b},\mathbf{a}}$ is positive definite

I came across this matrix as the covariance matrix of distribution when studying sparse Gaussian processes. Tried but couldn't prove it is pd.

Answer 1

The matrices $K_{a,a}$, $K_{b,b}$ are positive definite by construction.

Using the Schur complement the joint covariance matrix, which is also positive definite, can be decomposed into: $$ M = {\begin{bmatrix}K_{a,a}&K_{a,b}\\K_{b,a}&K_{b,b}\end{bmatrix}}={\begin{bmatrix}I&K_{a,b}K_{b,b}^{-1}\\0&I\end{bmatrix}}{\begin{bmatrix}K_{a,a}-K_{a,b}K_{b,b}^{-1}K_{b,a}&0\\0&K_{b,b}\end{bmatrix}}{\begin{bmatrix}I&0\\K_{b,b}^{-1}K_{b,a}&I\end{bmatrix}} $$ The eigenvalues of $M$, that is $\lambda(M)$, are equal to the set $\{\lambda(K_{a,a}-K_{a,b}K_{b,b}^{-1}K_{b,a}), \lambda(K_{b,b})\}$. Since all eigenvalues of $M$ are positive means that all eigenvalues of $K_{a,a}-K_{a,b}K_{b,b}^{-1}K_{b,a}$ are also positive. Then it can be shown that $K_{a,b} = K_{b,a}^\top$, and thus $K_{a,a}-K_{a,b}K_{b,b}^{-1}K_{b,a}$ is symmetric. Hence, $K_{a,a}-K_{a,b}K_{b,b}^{-1}K_{b,a}$ is a symmetric matrix with positive eigenvalues, and therefore is positive definite.