4
$\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 23:03

1 Answer 1

4
$\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 and acknowledge you have read our privacy policy.

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