Proving the following inequality (positive def. matrix)

I'm trying to prove (or disprove) the following:

$$ \sum_{i=1}^{N} \sum_{j=1}^{N} c_i c_j K_{ij} \geq 0$$ where $c \in \mathbb{R}^N$, and $K_{ij}$ is referring to a kernel matrix:

$$K_{ij} = K(x_i,x_j) = \frac{\sum_{k=1}^{N} \min(x_{ik}, x_{jk})}{\sum_{k=1}^{N} \max(x_{ik}, x_{jk})}$$ Here, $x \in \mathbb{R}^N \geq 0$.

I'm basically trying to prove that $K_{ij}$ is a positive definite matrix, so I can use it as a Kernel, but I'm really stuck trying to work with $\max$

Edit: the function I'm refering to is:

$$K(u,v) = \frac{\sum_{k=1}^{N} \min(u_{k}, v_{k})}{\sum_{k=1}^{N} \max(u_{k}, v_{k})}$$ where $u, v \in \mathbb{R}^N \geq 0$

Solution 1:

Fix $x_i\in\mathbb{R}^n$, $i = 1, 2, \ldots, N$. We will assume without loss of generality that no $x_i$ is identically $0$. Define $N\times N$ matrices $A = (\sum_{k=1}^n\min(x_{i(k)}, x_{j(k)}))$ and $B = (\sum_{k=1}^n\max(x_{i(k)}, x_{j(k)}))$, where $x_{(k)}$ denotes the $k$th coordinate of $x$. Note that $K = A\odot B^{\odot-1}$ where $\odot$ denotes the Hadamard product and $B^{\odot-1}$ is the Hadamard inverse (entrywise reciprocal) of $B$. By the Schur product theorem, it suffices to show that $A$ and $B^{\odot-1}$ are positive definite. We will use the fact that a positive linear combination of positive definite matrices is positive definite.

To show that $A$ is positive definite, note that $A$ can be written as the sum $A = \sum_{k=1}^n A_k$ with $A_k = \min(x_{i(k)}, x_{j(k)})$. It suffices to show that e.g. $A_1$ is positive definite. For $i \in [N]$, let $y_i = x_{i(1)}$. By conjugating $A_1$ by a permutation matrix, we may assume without loss that $y_1\leq y_2\ldots \leq y_N$. For $i \in [N]$, let $f_i\in\mathbb{R}^N$ denote the vector with $f_{i(j)} = 0$ for $j < i$ and $f_{i(j)} = 1$ for $j \geq i$. Then, setting $y_0 = 0$, \begin{equation}A_1 = \sum_{i=1}^N(y_i - y_{i-1})f_if_i^t \geq 0. \end{equation}

We now show that $B^{\odot-1}$ is positive definite. By scaling, we may assume that $x_{i(j)} \in [0, 1/n]$ for all $i$ and $j$. Using the identity $1/x = \sum_{i=0}^{\infty}(1-x)^i$ valid for $x\in (0, 2)$, we may write $B^{\odot-1} = J + \sum_{i=1}^{\infty} (J-B)^{\odot i}$, where $J=f_1f_1^t$ denotes the all ones matrix. Now \begin{equation}(J-B)_{ij} = 1 - \sum_{k=1}^n\max(x_{i(k)}, x_{j(k)}) = \sum_{k=1}^n \min(\frac{1}{n}-x_{i(k)}, \frac{1}{n}-x_{j(k)}). \end{equation} The above argument that showed that $A$ is positive definite now shows that $J-B$ is positive definite (by replacing $x_i$ with $x_i' = \frac{1}{n}f_1 - x_i$). Finally, the Schur product theorem and the fact that positive definite matrices are closed under positive linear combinations show that $B^{\odot-1}$ is positive definite.

Solution 2:

I have some comments in a different direction from g g. Maybe they'll be useful to someone.

First, like g g noted, $K \geq 0$ if $n = 1$, so the kernel matrix is semipositive there. For $n = 2$, the kernel matrix we get is of the form $$ B = \begin{pmatrix} 1 & a \\ a & 1 \end{pmatrix} $$ where $0 \leq a \leq 1$. By inspection, the eigenvectors of this matrix are $(1,1)$ and $(1,-1)$ with eigenvalues $1 + a$ and $1-a$, which are nonnegative, so the kernel matrix is semipositive.

In general, we have $\min(x,y) = \frac12(x + y - |x-y|)$ and $\max(x,y) = \frac12(x + y + |x-y|)$. Then $$ K(x,y) = \frac{\sum_j \min(x_j,y_j)}{\sum_j \max(x_j,y_j)} = \frac{|x+y|_1 - |x-y|_1}{|x+y|_1 + |x-y|_1}, $$ where $|\,\cdot\,|_1$ is the $1$-norm. I haven't been able to do anything with this so far.

This is close to some trigonometric identities: If we write $t(x,y) := \sqrt{|x-y|_1/|x+y|_1}$ then $K = (1-t^2)/(1+t^2)$ so if we set $t(x,y) =: \tan \theta(x,y)$ then $K = \cos 2\theta(x,y)$. But I don't know how to do anything useful with that in the quadratic form the kernel matrix $B$ defines.

As I said in a comment, we can have numpy crunch some randomly sampled examples:

https://pastebin.com/UGKrvxSK

This has only given me positive-definite matrices so far for $K$, while randomly sampling matrices with entries between $0$ and $1$ and $1$s on the diagonal yields matrices that are almost never positive-definite as $n$ grows, which seems like some kind of evidence for the kernel matrix being positive-definite in general.

Solution 3:

Warning: Only (very) partial answer!

For $N=1$ and $u,v>0$ the function $K$ is indeed positive definite in the sense normally used for a Kernel function (see here). This standard definition is different from the OP's since it requires the Kernel matrix to be positive for any set of $n$ points (instead of only for $N$ points as in the OP's question). This makes the general case already non-trivial for $N=1$, while it is of course obvious for $n=N=1$.

Observe that $$K(u,v) = \frac{\min(u,v)}{\max(u,v)}= \begin{cases} \frac{u}{v}\text{ if }u\leq v\\ \frac{v}{u}\text{ if }u\geq v. \end{cases}$$ Now set $u=\exp x$ and $v = \exp y$ and write $$ K(u,v)=K(\exp x, \exp y) = \exp \left(-\lvert x-y \rvert \right). $$ It is well known that $\exp \left(-\lvert x-y \rvert \right)$ is a positive definite Kernel. This kernel is known as Laplacian or Matern-$\frac{1}{2}$.

With respect to the domain of definition: Note that you can extend this Kernel continuously to $\mathbb{R}^{\geq 0}\times \mathbb{R}^{\geq 0} \setminus (0,0)$ by setting $K(0,u)=0$ for $u\neq 0$. But this fails in $(0,0)$ because $K(u,u)=1$ for $u\neq 0.$