14
$\begingroup$

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$

$\endgroup$
14
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Apr 25, 2021 at 20:24
  • 2
    $\begingroup$ @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.) $\endgroup$ Commented Apr 26, 2021 at 8:44
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Apr 27, 2021 at 20:18
  • 2
    $\begingroup$ @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)$. $\endgroup$
    – g g
    Commented May 1, 2021 at 6:40
  • 1
    $\begingroup$ I cannot make sense of your "Edit". What is the right definition ? $\endgroup$
    – user65203
    Commented May 4, 2021 at 7:07

3 Answers 3

7
+50
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Really elegant and clever! However, I would like to see if conjugating a PSD matrix keeps it PSD $\endgroup$
    – Norhther
    Commented May 10, 2021 at 10:46
  • $\begingroup$ 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. $\endgroup$
    – Anand
    Commented May 10, 2021 at 17:24
  • $\begingroup$ I'm afraid I'm not following you here. What exact operations does conjugating A by a permutation matrix are? $\endgroup$
    – Norhther
    Commented May 10, 2021 at 17:41
  • $\begingroup$ 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. $\endgroup$
    – Anand
    Commented May 10, 2021 at 17:59
  • $\begingroup$ yeah, I saw that the rearranging was really convenient, however I'm lost at finding $P$ such as $PAP^-1$ permutates columns and rows. $\endgroup$
    – Norhther
    Commented May 10, 2021 at 18:08
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – g g
    Commented Apr 30, 2021 at 18:56
  • $\begingroup$ 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. $\endgroup$ Commented Apr 30, 2021 at 19:00
  • 1
    $\begingroup$ You are right. But I suspect the OP has stated his requirement incorrectly. $\endgroup$
    – g g
    Commented May 1, 2021 at 6:48
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .