problem over positive definite kernel.

Question

I'm having the following problem for which I can't find a solution.

Let's consider two kernel, $ K(x,y)$ and $K'(x,y)$, function from $X^2 \rightarrow \mathbb{R}$ with $X$ an arbitrary set. I have the following property, $\forall (x,y), K(x,y) > K'(x,y)$ and kernel $K'$ is positive definite, meaning that the following property holds :

$$ \sum_{i=1}^n \sum_{j=1}^n c_i c_j K'(x_i,x_j) \geq 0$$

for $c_1,..,c_n \in \mathbb{R}$. Is it possible to show that in this case the kernel $K(x,y)$ is positive definite ? My intuition is that we can't infer anything on $K$ just from knowing $K(x,y) > K'(x,y)$.

Answer 1

It's not exactly clear what you are assuming about $K$, but it is not true that if a symmetric matrix (such as $A=\pmatrix{10&20\\20&10}$) is element-wise greater than a positive definite matrix (such as $B=\pmatrix{1&0\\0&1}$), that the first matrix must necessarily be positive definite. For example, $c=(1,-1)^T$ has the property that $c^TAC=-20$ but $c^TBc=2$.

If your assumption on $K$ is that its elements form a semi-positive definite matrix, and your question is, does the element-wise inequality $K>K'$ imply $K$ is strictly psd if $K'$ is, the answer is no. $A=\pmatrix{10&10\\10&10}$ gives an example of a semi-definite matrix which is strictly element-wise greater than a strictly positive definite matrix.