3
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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$ $\endgroup$ – Glen_b Feb 26 '14 at 22:44
  • $\begingroup$ @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. $\endgroup$ – Danny Feb 26 '14 at 22:48
  • $\begingroup$ 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$. $\endgroup$ – whuber Feb 26 '14 at 22:50
  • $\begingroup$ Good time to check the definitions. What's the definition you have of a psd function? $\endgroup$ – Glen_b Feb 26 '14 at 22:50
  • 1
    $\begingroup$ @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. $\endgroup$ – Danny Feb 26 '14 at 23:03
3
$\begingroup$

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

$\endgroup$

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.