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.

  • $\begingroup$ 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 $\endgroup$ – g g Mar 16 at 8:22
  • $\begingroup$ @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. $\endgroup$ – Shashank Kumar Mar 16 at 8:38
  • $\begingroup$ Also number of a_i’s and b_i’s are in general not equal $\endgroup$ – Shashank Kumar Mar 16 at 8:40
  • $\begingroup$ These number do not really change the problem $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.