1
$\begingroup$

I have an exercise in my book, which I'm not sure if I have answered correctly. Here's the exercise:

For the function $K: \mathbb{R}^2\times \mathbb{R}^2\to \mathbb{R}$ such that $$K(x,t)=x^TDt$$, where $$D=\begin{pmatrix} -1 && 2 \\ 2 &&4 \end{pmatrix}$$

Determine whether the function is a valid kernel (i.e., the kernel can be written as an inner product in some feature space) and when the answer is positive derive an associated feature map representation.

In this question, it is said that we have to check that the funciton $k(x,t)$ is symmetric and also whether it is positive definite. So, the function is symmetric. We need to check if it's PSD.

We check it by inspecting for an "inner-product" representation. I would like to find a $\phi(a)$, such that $k(x,t)=\phi(x)^T\phi(t)$. Well, $$\phi(a)=(ia_1,\sqrt{2}a_1,\sqrt{2}a_2,2a_2)^T$$

Hence, $K$ is a valid kernel.

EDIT

There is no such function, because the indices in $K(x,t)=x^TDt=-x_1t_1+2x_2t_1+2x_1t_2+4x_2t_2$ are "mixed", i.e., $x_1$ is multiplied by $t_2$, so there is no such function $\phi(a)$.

Hence $K$ is not a valid kernel.

Is this correct?

$\endgroup$
2
  • 1
    $\begingroup$ Hint: What is $K((1,0), (1,0))$? $\endgroup$
    – whuber
    Oct 25, 2021 at 13:56
  • 2
    $\begingroup$ @whuber it's $-1$, yes I know that it's less than $0$ hence it doesn't satisfy the conditions of an inner product space, positive definiteness in this case. $\endgroup$
    – Slim Shady
    Oct 25, 2021 at 16:17

1 Answer 1

2
$\begingroup$

Checking $K((1,0), (1,0)) < 0$ rules out that the possibility that it can be a kernel.

Checking whether $x^TDx$ is a valid kernel is equivalent to checking if $D$ is positive semidefinite.

Mixing indices can occur in matrix in the expression of $K(x,t)$, for example if $D=\begin{bmatrix} 4 & 2 \\ 2 & 4\end{bmatrix}$, then $K$ is a valid kernel since it is positive semidefnite.

$\endgroup$
3
  • $\begingroup$ When you say that checking whether $K(x,y)$ is a kernel is a question of whether $D$ is positive SD. But why is that so? I know that if $D$ is psd then $K$ is a kernel, but why would the converse be true? $\endgroup$
    – Slim Shady
    Oct 26, 2021 at 11:06
  • 1
    $\begingroup$ Suppose $D$ is not positive semidefinite, then it is possible to find $x$ such that $x^TDx < 0$, which violate Mercer's theorem. $\endgroup$ Oct 26, 2021 at 16:05
  • $\begingroup$ oh yes, that's true. thanks for the answer! $\endgroup$
    – Slim Shady
    Oct 26, 2021 at 16:43

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.