How to prove the following kernel $K$ over $\mathbb R \times \mathbb R$ is positive semi-definite: $$K(x_i, x_j) = e^{-\lambda[\sin(x_i - x_j)]^2},$$ where $\lambda > 0$. It looks like the gaussian kernel $e^{-\lambda\|x_i - x_j\|^2}$. How can we link $\sin$ function to some kinds of norm?

Or equivalently, how to prove the matrix $A$ defined by $$A_{ij} = e^{-\lambda[\sin(x_i - x_j)]^2}$$ is positive semi-definite for any $\lambda > 0$ and $x_1, \cdots, x_n > 0$?


I doubt that this is the best approach since it basically only uses the definition of positive semidefinite (PSD) matrices and requires a fact about the pointwise product of PSD matrices, but maybe it will give you some ideas.

We have that, $$ \sin(x_i-x_j)^2 = \frac{1}{2} - \frac{1}{2}\cos(2(x_i-x_i)) = \frac{1}{2} - \frac{1}{2}\big[ \cos(2x_i)\cos(2x_j) + \sin(2x_i)\sin(2x_j) \big] $$

Therefore we can write, $$ A_{i,j} = e^{-\lambda/2}\exp\left(\frac{\lambda}{2}\cos(2x_i)\cos(2x_j) +\frac{\lambda}{2}\sin(2x_i)\sin(2x_j) \right) $$

Now, note that the matrix, $$ B_{i,j} = \frac{\lambda}{2}\cos(2x_i)\cos(2x_j) + \frac{\lambda}{2}\sin(2x_i)\sin(2x_j) $$ is the sum of two rank-1 outer products and therefore PSD.

Note: Maybe for your needs its sufficient to show the part of the kernel in the exponent is the sum of separable functions, in which case you are done.

Using Taylor expansion we have, $$ A_{i,j} %= e^{-\lambda/2} \sum_{k=0}^{\infty} \frac{1}{k!} \left( \frac{\lambda}{2}\cos(2x_i)\cos(2x_j) + \frac{\lambda}{2}\sin(2x_i)\sin(2x_j) \right)^k = e^{-\lambda/2} \sum_{k=0}^{\infty} \frac{1}{k!} B_{i,j}^k $$

So in matrix form, using $\circ$ to denote the poitwise product of matrices, $$ A = e^{-\lambda/2} \left( I + B + \frac{1}{2!} B\circ B + \frac{1}{3!} B\circ B\circ B + \cdots \right) $$

Finally, we claim that this matrix is PSD. First, note that the pointwise product of two PSD matrices is again PSD. Therefore, each of the terms $B\circ B\circ \cdots \circ B$ is PSD. The sum of PSD matrices is also PSD.

This is an infinite series of pointwise additions and products of PSD matrices. If this converges (which you know it does), it will also be PSD.

  • $\begingroup$ I wonder if you left $1$ in the formula. I think we need to prove $A_{i,j} = \cos(2x_i)\cos(2x_j) + \sin(2x_i)\sin(2x_j) - 1$ is PSD, and then we can use the fact that "positive semi-definite kernels are closed under sum, product, tensor product, pointwise limit, and composition with a power series". However $A_{i,j} = \cos(2x_i)\cos(2x_j) + \sin(2x_i)\sin(2x_j) - 1$ is not PSD. $\endgroup$ – Rubisco Lee Dec 24 '18 at 15:54
  • $\begingroup$ I pulled the $-\lambda/2$ out of the matrix as a constant in front. Since you end up with $e^{-\lambda/2} > 0$ as the constant, it won't change that the matrix is PSD $\endgroup$ – tch Dec 24 '18 at 16:00
  • $\begingroup$ Yes you are right. Actually I was just stuck on how to deal with the $1$. I forgot that we can just move it out since it is the exp function... Thanks a lot for your help! $\endgroup$ – Rubisco Lee Dec 24 '18 at 16:15

A sensible approach may be to use that $\cos(2\tau)$ is a characteristic function, and so positive semi-definite, and build from there.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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