2

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.

Shashank Kumar
  • 31
  • 2
  • 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](https://stats.stackexchange.com/questions/187341/effect-of-measurement-variance-on-predictive-variance-in-gaussian-processes/187637#187637) – g g Mar 16 '21 at 08: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 '21 at 08:38
  • Also number of a_i’s and b_i’s are in general not equal – Shashank Kumar Mar 16 '21 at 08:40
  • These number do not really change the problem – g g Mar 16 '21 at 08:42

1 Answers1

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.

hakanc
  • 516
  • 3
  • 8