For every x, y ∈ IN = {1, . . . , N} define K(x, y) = min{x, y}. Prove that K is a valid kernel

Question

I need to prove K is a valid Kernel. x and y are positive integers, and K is the minimum of x and y. I know I should prove K positive definite. But May I see how.

Answer 1

Let $\mathcal X$ be any subset of $\{1...N\}$, and $|\mathcal X|=n,$ and $x_i,x_j$ be any two elements from this set.

We can write $\min(x_i,x_j)$ as below: $$\min(x_i,x_j)=\int_0^N \mathbb 1(t\leq x_i)\mathbb 1(t\leq x_j)dt$$

The reason of this equality is straightforward. The first indicator function will be $1$ until $x_i$; and the second indicator function is $1$ until $x_j$. The multiplication will be $1$ if both are $1$, which means until the minimum of $x_i$ and $x_j$. The integral then can be written as $$\begin{align}\int_0^N\mathbb 1(t\leq x_i)\mathbb 1(t\leq x_j)dt&=\int_0^{\min(x_i,x_j)}\mathbb 1(t\leq x_i)\mathbb 1(t\leq x_j)dt\\&=\int_0^{\min(x_i,x_j)}1\times 1\times dt\\&=\min(x_i,x_j)\end{align}$$

Then, we substitute in to the PSD requirement: $$\begin{align}\sum_{i=1}^n\sum_{j=1}^n c_i c_j \min(x_i,x_j)&=\sum_{i=1}^n\sum_{j=1}^n c_i c_j \int_0^N \mathbb 1(t\leq x_i)\mathbb 1(t\leq x_j)dt \\&=\int_0^N \underbrace{\left(\sum_{i=1}^n c_i\mathbb 1(t\leq x_i)\right)}_{M(t)}\underbrace{\left(\sum_{j=1}^n c_j\mathbb 1(t\leq x_j)\right)}_{M(t)}dt\\&=\int_0^NM(t)M(t)dt=\int_0^NM(t)^2dt\geq 0\end{align}$$

Both multiplicands are equal because both summations range from $1$ to $n$. We can also change the order of summations and integrations according to Fubini's theorem (in short, the sums and integrals are finite).

This covers PSD property and you've already mentioned the symmetric property in your comment.

Answer 2

Let $B_1, B_2, \ldots, B_N, \ldots$ be a sequence of independent zero-mean unit variance random variables. For instance, each $B_i$ could be a Rademacher variable that has a $1/2$ chance of being $+1$ and a $1/2$ chance of being $-1.$

Let $X_i = B_1 + B_2 + \cdots + B_i$ be the partial sum. The sequence $(X_i)$ is an example of a random walk. We are going to compute the covariance matrix of this walk. The algebra is simple, but I will give all the details just to be perfectly clear.

Because each $X_i$ is a sum of independent (therefore uncorrelated) variables, its variance is the sum of the variances of its components, whence $$\operatorname{Var}(X_i) = \operatorname{Var}(B_1) + \operatorname{Var}(B_2) + \cdots + \operatorname{Var}(B_i) = i.$$

Morever, when $j\gt i$ the additional terms in $X_j$ (namely, $B_{i+1} + \cdots + B_j$) are independent of $X_i$ and therefore uncorrelated with it, showing that

$$\begin{aligned} \operatorname{Cov}(X_i, X_j) &= \operatorname{Cov}(X_i, X_i + (X_j-X_i))\\ & = \operatorname{Cov}(X_i,X_i) + \operatorname{Cov}(X_i, X_j-X_i) \\ &= \operatorname{Var}(X_i) + 0 \\ &= i. \end{aligned}$$

Since covariance is symmetric, $$\operatorname{Cov}(X_j,X_i) = \operatorname{Cov}(X_i,X_j) = i.$$

A convenient way to express all these results is

$$\operatorname{Cov}(X_i,X_j) = \min(i,j) = K(i,j).$$

Because $K$ is a covariance matrix and all covariance matrices are positive semi-definite, it is a kernel, QED.

Answer 3

Here is a simple way to prove the positive semi-definiteness of the kernel $ k(x, y) = \min(x, y)$.

By Mercer's theorem, we know that $k(x, y)$ is a kernel iff it can be written as $k(x, y) = \langle\phi(x), \phi(y)\rangle$.

Now, let us define, $\phi(x): \mathcal{X} \rightarrow \mathbb{R}^N$, as $\phi(x) = \operatorname{Concat}( \mathbf{1} \in \mathbb{R}^x, \mathbf {0} \in \mathbb{R}^{N-x}) $. In words, it is basically a function that returns a vector with $x$ ones, followed by $N-x$ zeros.

Now, we can simply verify that, in fact, $\min(x, y) = \langle\phi(x), \phi(y)\rangle ~~\forall x, y \in \mathcal{X}$. Hence, by Mercer's theorem, the minimum function is a kernel.

We can also see that by the properties of kernels, $k(\phi(x), \phi(y))$ is a kernel, and that $\langle\cdot,\cdot\rangle$ is a kernel, making the minimum function a kernel.