# how to prove this kernel function is positive semidefinite

How to prove $k(x_i,x_j)=e^{-(LR(x_i-x_j))^TLR(x_i-x_j)}$ is a valid kernel function or positive semi definite?

$x=(\mu,\lambda)^T$ and R is a 2x2 rotation matrix, L is a 2x2 diagonal scaling matrix with positive entries. Any idea is appreciated.

• So you need the quadratic in the in the $e^{-...}$ to be $\geq$. You should be able to make an argument why that implies you just need $R^TL^TLR$ to be psd. If $R$ is a rotation matrix, you should be able to make an argument that you just need $L^TL$ to be psd. If L is diagonal with positive entries ... etc. OR alternatively, I suppose, just expand the whole thing out and argue why that's $\geq 0$ – Glen_b Feb 26 '14 at 22:44
• @Glen_b I am able to see and prove that $R^TL^TLR$ is psd. But I am not sure how to get to the conclusion that $k(x_i,x_j)$ is a psd function if $R^TL^TLR$ is a psd matrix. – Danny Feb 26 '14 at 22:48
• The meanings of "valid" and "kernel" depend (unfortunately) on the application: they have different (although) related meanings for kernel density estimation and in the "kernel trick" for SVMs, for instance. What is your meaning? BTW, as $x_i$ and $x_j$ range through all possible vectors, $R(x_i-x_j)$ ranges through all possible vectors, so you only need to show that $y^\prime L^\prime L y\gt 0$ for all nonzero vectors $y$. – whuber Feb 26 '14 at 22:50
• Good time to check the definitions. What's the definition you have of a psd function? – Glen_b Feb 26 '14 at 22:50
• @Glen_b From the definition, if we have n input, that requires the matrix of nxn $[k_{i,j}]_{i,j=1}^n$ is psd. – Danny Feb 26 '14 at 23:03

Let $A = L R$; then your kernel is $k(x, y) = \exp(- (x-y)^T A^T A (x-y) )$. It's then clear that this an RBF kernel on a linear transformation of the input space, i.e. \begin{gather*} \tilde{k}(x, y) = \exp(- \|x - y\|^2) \\ k(x, y) = \tilde{k}(A x, A y) \end{gather*} As is well-known, the RBF kernel $\tilde{k}$ is psd; see e.g. this question for a proof.
One way to characterize positive semidefiniteness is that for all points $x_1, \dots, x_m$ in $\mathbb{R}^n$ (in your question, $n=2$) and numbers $a_1, \dots, a_m$, we have $$\sum_{i=1}^m \sum_{j=1}^m a_i a_j k(x_i, x_j) \ge 0 .$$ We know this holds for $\tilde{k}$ and wish to show it for $k$. But that sum is $$\sum_{i=1}^m \sum_{j=1}^m a_i a_j k(x, y) = \sum_{i=1}^m \sum_{j=1}^m a_i a_j \tilde{k}(A x_i, A x_j) = \sum_{i=1}^m \sum_{j=1}^m a_i a_j \tilde{k}(\tilde{x_i}, \tilde{x_j}) \ge 0,$$ using the condition for $\tilde{k}$ with points $\tilde{x_i} = A x_i$ and numbers $a_i$.