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$$

• Ok, I would usually write $x^{(i)}$ for the vector and $x^{(i)}_k$ for the $k$th entry of the $i$th vector, then it is clear, which variable is for the sequence of vectors and which one is meant for the entry (but that is personal preference). The notation $x_{ik}$ makes not much sense, $(x_i)_k$ would be slightly better, but quite ugly. Enough ranting about notation :D I'll think abou the problem. Commented Apr 25, 2021 at 20:24
• @Rammus My interpretation of the construction is: Pick vectors $x_1, \ldots, x_N \in \mathbb R^N$ and define a matrix $K = (K_{ij})$, where $K_{ij} = K(x_i, x_j)$. The question is then whether the symmetric form defined by $K$ is (semi) positive-definite. But you're right that the function $K$ itself is not homogeneous (we only have $\alpha K(x, y) = K(\alpha x, \alpha y)$) and does not define an inner product. ("Semi"-positive because if all the $x_j$ are equal we only get a semipositive matrix.) Commented Apr 26, 2021 at 8:44
• I've been trying to find a counterexample and am starting to lean towards this actually being true. In dimension 2 this is true. In dimension 3 (and higher), the matrix we get has 1 on the diagonal and the entries off-diagonal are between 0 and 1. Those matrices are not all positive-semidefinite. However, no matter how I try to pick my vectors, I can't land in a region of non-semidefinite matrices. I had numpy crunch through a few million examples in dimensions 5 and 10 and it didn't find a counterexample. Commented Apr 27, 2021 at 20:18
• @Norhther: The definition you are checking is different from the requirement for a Kernel function. Are you sure this is what you need? In fact, the standard definition of positive definite would require a general $n$ instead of the dimension of the domain $N$. Check also the domain of definition. I do not think your function works in $(0,0)$.
– g g
Commented May 1, 2021 at 6:40
• I cannot make sense of your "Edit". What is the right definition ?
– user65203
Commented May 4, 2021 at 7:07

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$$, $$$$A_1 = \sum_{i=1}^N(y_i - y_{i-1})f_if_i^t \geq 0.$$$$

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 $$$$(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)}).$$$$ 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.

• Really elegant and clever! However, I would like to see if conjugating a PSD matrix keeps it PSD Commented May 10, 2021 at 10:46
• Thanks! Conjugating any matrix $X$ by an invertible matrix $U$ preserves its spectrum, since e.g. if $Xv = \lambda v$, then $UXU^{-1}(Uv) = \lambda(Uv)$. In particular, being PSD is preserved by conjugation. Commented May 10, 2021 at 17:24
• I'm afraid I'm not following you here. What exact operations does conjugating A by a permutation matrix are? Commented May 10, 2021 at 17:41
• If $P$ is a permutation matrix, then $PAP^{-1}$ is the matrix $A$ with rows and columns rearranged according to $P$. The eigenvalues of both matrices are the same (so if $A$ is PSD, so is $PAP^{-1}$). The reason I use this in the proof is for convenience, so we can assume the $y_i$'s are in increasing order. Commented May 10, 2021 at 17:59
• yeah, I saw that the rearranging was really convenient, however I'm lost at finding $P$ such as $PAP^-1$ permutates columns and rows. Commented May 10, 2021 at 18:08

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.

• Maybe I am confusing your $n$ with the OP's $N$ but I do not understand why you say a Kernel with $N=2$ is 2-by-2. The size of the Kernel matrix is unrelated to the dimension of the domain. If you have $n$ points the Kernel matrix is $n$-by-$n$ no matter the dimension of the domain.
– g g
Commented Apr 30, 2021 at 18:56
• My $n$ is the OP's $N$. The original question defines a kernel function $K$ on a subset of $\mathbb R^N$ and then picks $N$ vectors $x_1, \ldots, x_N$ to form a kernel matrix $(K(x_j, x_k))$. You're right that we could pick fewer or more vectors in $\mathbb R^N$, but that doesn't seem to be what the question here does. Commented Apr 30, 2021 at 19:00
• You are right. But I suspect the OP has stated his requirement incorrectly.
– g g
Commented May 1, 2021 at 6:48

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.$$