2
$\begingroup$

For such a kernel:

$$K(x, y) = \min(x, y) - xy \text{ over } [0, 1] \times [0, 1].$$

How can I prove that it's positive semi definite? I know how to prove $\min(x, y)$ is PSD but I think $-xy$ is NSD, so can't use the closure property here. Is there a good approach?

$\endgroup$
3
  • 1
    $\begingroup$ It might help to note that $K(x,y) = \min(x,y) - \max(x,y)*\min(x,y) = \min(x,y)*(1-\max(x,y)) \geq 0$. $\endgroup$
    – jbowman
    Dec 1, 2017 at 22:44
  • 1
    $\begingroup$ where does this statement come from? @jbowman, how does your hint help? The PSD is different from non-negativity. $\endgroup$
    – Zhanxiong
    Dec 1, 2017 at 23:02
  • 1
    $\begingroup$ I'll extend the hint. Can you show that $1-\max(x,y)$ is PSD? Then you have the product of two symmetric PSD functions... $\endgroup$
    – jbowman
    Dec 1, 2017 at 23:54

2 Answers 2

2
$\begingroup$

To show that $K(x, y)$ is positive semi-definite (PSD), it is sufficient to show that for any $n$ and $x_1, \ldots, x_n \in [0, 1]$, the Gram matrix $G = (K(x_i, x_j)) \in \mathbb{R}^{n \times n}$ is PSD. To this end, we use the following two properties in linear algebra:

  1. For $a_i \in [0, 1], i = 1, \ldots, n$, the matrix $A = (\min(a_i, a_j)) \in \mathbb{R}^{n \times n}$ is PSD.
  2. If two matrices $M_1$ and $M_2$ are PSD, then their Hadamard product $M_1 \circ M_2$ is also PSD.

If we can prove $1$ and $2$, then $M_1 = (\min(x_i, x_j)) \geq 0$, $M_2 = (\min(1 - x_i, 1 - x_j)) \geq 0$ and $G = M_1 \circ M_2$ together imply that $G \geq 0$. This completes the proof.


Proof of 1. Since $\min(a_i, a_j) = \int_0^1 I_{(0, a_i]}(t)I_{(0, a_j]}(t)dt$, where $I_A(\cdot)$ stands for the indicator function (writing the entry $a_{ij}$ in appropriate integral form is a routine way to prove the positive definiteness of $A$, here is another example), for any $z := (z_1, \ldots, z_n) \in \mathbb{R}^n$, it follows that \begin{align} & z'Az \\ =& \sum_i\sum_j z_iz_j\min(a_i, a_j) \\ =& \sum_i\sum_j z_iz_j\int_0^1 I_{(0, a_i]}(t)I_{(0, a_j]}(t)dt \\ =& \int_0^1 \sum_i z_i I_{(0, a_i]}(t)\sum_j z_j I_{(0, a_j]}(t)dt \\ =& \int_0^1\left(\sum_i z_i I_{(0, a_i]}(t)\right)^2dt \geq 0. \end{align} This proves that $A$ is PSD.

Proof of 2. The result is known as Schur product theorem, and the proof can be found in the same link.

$\endgroup$
5
  • $\begingroup$ Is it true in general that you can check whether a kernel is psd by checking every two-by-two matrix M(x,y)? I thought that in general you need to check every n-by-n matrix, for arbitrary n. $\endgroup$
    – Jasha
    May 14, 2018 at 0:08
  • $\begingroup$ So typically the kernel is a function $\mathcal X^n\to\mathbb R$, where $n$ is $2$. By "the number of variables contained in the kernel", are you referring to this number $n$? Any references would be much appreciated. Thanks. $\endgroup$
    – Jasha
    May 14, 2018 at 13:00
  • 1
    $\begingroup$ The Gram matrix is an $n \times n$ matrix where $n$ is the number of rows (data points). $x, y$ being scalars only implies that the number of features for each row is 1; the Gram matrix can be much larger, so this answer is wrong $\endgroup$ Sep 22, 2018 at 5:54
  • 2
    $\begingroup$ I feel the answer is wrong, too. I think that you need to prove that for any number of any points $x1,...,x_l$, the Gram matrix is psd. $\endgroup$ Apr 25, 2019 at 14:56
  • $\begingroup$ @TomBennett You are right. Previously I didn't understand the concept sufficiently well. Now I have updated the answer! $\endgroup$
    – Zhanxiong
    Feb 26, 2023 at 5:18
-1
$\begingroup$

Thanks to hint from jbowman. Here's my thought:

Since K(x, y) is guaranteed to be greater than or equal to 0, all elements in the Gram matrix will be greater than or equal to 0. Then all eigen values of the Gram matrix will be non-negative, so kernel K is PSD.

Edit:

Yes you guys are right, I seriously have to pick up my linear algebra.

To show that 1 - max(x, y) is PSD. We can treat that as we do to min(x, y), 1 - max(x, y) over [0, 1] is equivalent to $\int_0^11_{t>x}1_{t>y}dt$

\begin{eqnarray*} \sum_{i, j}c_ic_j\int_0^11_{t>x}1_{t>y}dt&=&\int_0^1(\sum_1^nc_i1_{t>x})(\sum_1^nc_j1_{t>y})dt\\&=&\int_0^1Z^2(t)dt\\&\geq&0 \end{eqnarray*}

Hope I didn't mess up anything this time.

$\endgroup$
3
  • 1
    $\begingroup$ The gram matrix requires its elements to be of the form $K(v_i,v_j)=\langle v_i,v_j\rangle$. Without this condition, it doesn't have to be positive definite (nor a gram matrix). $\endgroup$
    – Alex R.
    Dec 1, 2017 at 23:22
  • 6
    $\begingroup$ You seem to be invoking false theorems in this reasoning. For instance, all entries in the symmetric real matrix $$\pmatrix{1&2\\2&1}$$ are positive, but it (obviously) has a negative eigenvalue. $\endgroup$
    – whuber
    Dec 1, 2017 at 23:39
  • $\begingroup$ There is indeed a theorem that states that a symmetric matrix A is positive definite if and only if all the eigenvalues are positive. But I think you've got muddled into thinking PSD is true when all the elements of symmetric matrix A are >=0, whereas in fact it's x^T A x that must be >=0 for all x. $\endgroup$
    – beldaz
    Sep 12, 2018 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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