I am trying to determine the functions $\phi : \mathbb{R}^+ \to \mathbb{R}$ such that:

Pb 1: $K(s, t) = \phi( \mathrm{min} (s,t))$ is a positive definite kernel on $\mathbb{R}^+$.

Pb 2: $K(s, t) = \phi( \mathrm{max} (s,t))$ is a positive definite kernel on $\mathbb{R}^+$.

(NB: The 2 problems are independent, I am not trying to find functions statisfying BOTH conditions)

For Pb1, since min is a p.d. kernel, I have found that all $\phi$ admitting a power series expansion on $\mathbb{R}^+$ with positive coefficients will work (e.g. polynoms with positive coeffs, exponential). By Cauchy-Schwarz inequality, I also found that $\phi$ must be increasing.

For Pb2, Cauchy-Schwarz gives that $\phi$ must be decreasing. It must also take positive values. I have found that positive constant functions work, and I wonder if they are the only ones.

Any hints?


It appears that the increasing (resp. decreasing) condition, along with $\phi$ taking positive values, is sufficient for Pb 1 (resp Pb 2).

I have found 2 proofs. The first one is quite technical and involves semi-characters of ($\mathbb{N}$, max, Id). The second one is a bit clever and I'll write it here:

Let $\phi$ such that $K(s, t) = \phi(\mathrm{min}(s, t))$ is a positive definite kernel on $\mathbb{R}_+^2$.

For all $x \in \mathbb{R}_+, \phi(x) = K(x, x) \geq 0$ so $\phi$ must take positive values.

$K$ must satisfy Cauchy-Schwarz inequality. Let $x, y \in \mathbb{R}_+$ such that $x \leq y$. We must have $K(x, y) ^2 \leq K(x, x) K(y, y)$, that is $\phi(x)^2 \leq \phi(x) \phi(y)$.

If $\phi(x) = 0$, then $\phi(y) \geq 0 = \phi(x)$.

Else, $\phi(x) > 0$ and we can divide the inequality by $\phi(x)$, which yields $\phi(x) \leq \phi(y)$. So $\phi(x) \leq \phi(y)$ in any case. So $\phi$ must be increasing.

Conversely, let $\phi$ be an increasing function taking positive values. Let $n \in \mathbb{N}^*$, let $a_1, ..., a_n \in \mathbb{R}$, let $t_1, ... , t_n \in \mathbb{R}_+$. Up to a reordering, assume $t_1 \leq ... \leq t_n$.

We want to show that $\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} a_i a_j \phi(\mathrm{min}(t_i, t_j)) \geq 0$

Here we use a trick: for any $x \geq 0, x = \int_0^{\infty} \mathbb{1}_{\{ s \leq x\}}. \mathrm{ds}$

So the desired quantity is equal to $\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n}\int_0^{\infty} a_i a_j \mathbb{1}_{\{ s \leq \phi(\mathrm{min}(t_i, t_j))\}}$

And since $\phi$ is increasing, $\mathbb{1}_{\{ s \leq \phi(\mathrm{min}(t_i, t_j))\}} = \mathbb{1}_{\{ s \leq \phi(t_i)\}} \mathbb{1}_{\{ s \leq \phi(t_j)\}}$

So our quantity is equal to $\int_0^{\infty} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} a_i a_j \mathbb{1}_{\{ s \leq \phi(t_i)\}} \mathbb{1}_{\{ s \leq \phi(t_j)\}}$

which is just $\int_0^{\infty} \left( \sum\limits_{i = 1}^{n} a_i \mathbb{1}_{\{ s \leq \phi(t_i)\}} \right)^2$ and this is a positive number.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.