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

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.

• to prove it symmetric is easy; k(x,y) = min{x,y} = min{y,x} = k(y,x) but how can I prove positive semi-definite: I need to show v^{T}Kv > 0 or show that sum(sum(c_x c_y K(x,y))) >= 0 Commented Jun 13, 2022 at 10:22
• x, y belong to I = {1, 2, , ..., N} Commented Jun 13, 2022 at 13:46
• Immediate proof: $K$ is the covariance matrix of Brownian motion on $\{1,2,\ldots, N\}.$
– whuber
Commented Jun 15, 2022 at 13:17

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.

• Can you please explain how you wrote the min in an integral form. Commented Jun 13, 2022 at 10:25
• It's a common trick. Do you understand it equals to min(x,y)? Commented Jun 13, 2022 at 10:29
• No, I didn't really get it Commented Jun 13, 2022 at 10:38
• I have added some explanation for it. Let me know if it's more understandable. Commented Jun 13, 2022 at 10:45
• yeah it is vert clear, thank you sir! Commented Jun 13, 2022 at 10:54

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.

• Quite interesting perspective! There is small typo, it should be like the following I believe: $\operatorname{var}(X_i)=\operatorname{var}(B_1)+...$ Commented Jun 18, 2022 at 12:48
• @gunes LOL -- I am constantly surprised at what I manage to overlook.
– whuber
Commented Jun 18, 2022 at 14:21

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.