Inequality on numerical range of inverse of kernel matrix

Question

Let $k(.,.)$ be a function that takes two vectors as input and outputs a scalar as follows \begin{align} \mathcal{k}(x,y) = \exp\left(-\frac{\|x-y\|_2^2}{2}\right) \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}

Answer 1

The radial basis function kernel $\mathcal{k}(x,y) = \exp\left(-\frac{\|x-y\|_2^2}{2\sigma^2}\right)$ 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.

Answer 2

A less elegant way to prove this would be to note that

$$(\mathbf K^{-1}\mathcal{K}_x)_i = \sum_jK^{-1}_{ij}K_{jx}= \begin{cases} 1 & i=x\\ 0 & i \not = x \end{cases}, $$

which is exactly $e_x$, the vector with a 1 in the $x$ coordinate and 0s elsewhere. We then remember that $\mathcal{K}_x$ is less than 1 in each component since $e^{-y} \leq 1$ for all $y \in [0,\infty]$ and then this gives us that $$\mathcal{K}_x^T\mathbf K^{-1}\mathcal{K}_x = \mathcal{K}_x^Te_x = k(x,x) = 1, $$

so the inner product is in fact 1. This generalizes to all invertible symmetric matrices with all diagonal elements $\leq$ 1.