# Prove that the following matrix is positive definite

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.

• The $a_i$ and $b_j$ span two subspaces. Use $K$ as a scalar product and observe that the expression gives you the projection of elements from a-space on b-space. See also my answer to this question – g g Mar 16 at 8:22
• @g g Sorry, I made a mistake in my question. Dimension of inputs could be anything. Not in general equal to number of training examples n. Sorry for that. – Shashank Kumar Mar 16 at 8:38
• Also number of a_i’s and b_i’s are in general not equal – Shashank Kumar Mar 16 at 8:40
• These number do not really change the problem – g g Mar 16 at 8:42

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.