Let $k(.,.)$ be a function that takes two vectors as input and outputs a scalar as follows \begin{align} \mathcal{k}(x,y) = \exp(-\frac{||x-y||_2^2}{2}) \end{align} where $||x||_2$ denotes the $2-$norm. Now, let $x_1,\dots,x_m$ be $m$ vectors in $\mathbb{R}^d$. Let me define the $m \times m$ matrix $\mathbf{K}$ such that its entries are given as \begin{align} \mathbf{K}_{ij} = \mathcal{k}(x_i,x_j) \end{align} For any vector $x$, let me define the $m\times 1$ vector $\mathcal{K}_x$ as \begin{align} \mathcal{K}_x = \begin{bmatrix} \mathcal{k}(x,x_1) \\ \vdots \\ \mathcal{k}(x,x_m) \end{bmatrix} \end{align} Now I am curious if following inequality holds true for every $x\in\mathbb{R}^d$ \begin{align} \mathcal{K}_x^T\mathbf{K}^{-1}\mathcal{K}_x \leq 1 \end{align}
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The radial basis function kernel $\mathcal{k}(x,y) = \exp(-\frac{||x-y||_2^2}{2\sigma^2})$ is a positive definite kernel. So, $M=\begin{bmatrix}\textbf{K}&\mathcal{K}_x\\\mathcal{K}_x^T&1\end{bmatrix} $ is a positive definie matrix. Hence, the Schur complement of the block $1$ of the matrix $M$ is also a positive definie matrix. That is $1-\mathcal{K}_x^T\mathbf{K}^{-1}\mathcal{K}_x \geq 0$. Q.E.D.
