# Checking if a kernel is valid

The kernel is $$K(x,z) = \sum_{i=1}^D (x_i+z_i)$$

My approach was trying to express $$K = \phi(x)^T\phi(z) = (x_1 x_2 ... x_D \quad 1 1 ...1)(1 1 ...1\quad z_1 z_2 ... z_D )^T$$ where $$\phi$$ is 2Dx1

The solution says:

K is not a kernel. Consider $$x_1 = [1 \quad 0]^T \quad x_2 = [0 \quad 2]^T$$. Their kernel matrix has eigenvalues −1 and 5.

What explains this discrepancy?

[EDIT]: Based on the link below and the given $$x_1, x_2$$, I arrive at $$S = 2a_1^2+6a_1a_2+4a_2^2$$ Now, how can I choose $$a_1,a_2$$ to make this negative?

• You can't show that a kernel is valid by constructing a single example which looks good, but you can show it's invalid by constructing a single example which looks bad (in this case, not positive definite.) See for example stats.stackexchange.com/questions/183215/…, which may be helpful. Commented Oct 13, 2018 at 2:33
• @jbowman: Please see edit above.
– db18
Commented Oct 13, 2018 at 17:05
• You might be interested in this thread: stats.stackexchange.com/questions/199620/…
– Sycorax
Commented Oct 13, 2018 at 17:14
• Response to edit: $S$ factors as $2(a_1+a_2)(a_1+2a_2)$, which will be negative if $a_1+a_2 > 0$ and $a_1+2a_2 < 0$, for example, $a_1 = 3$ and $a_2 = -2$. Commented Oct 13, 2018 at 17:36
• @jbowman: Thanks! Btw, how do I arrive at the eigenvalues mentioned in the original solution?
– db18
Commented Oct 13, 2018 at 18:04

Based on the link below and the given $$x_1, x_2$$, I arrive at $$S = 2a_1^2+6a_1a_2+4a_2^2$$ Now, how can I choose $$a_1,a_2$$ to make this negative?

We can factorize $$S$$ to obtain $$S = 2(a_1 + a_2) (a_1 + 2 a_2)$$ so if we want $$S < 0$$, we need to choose $$a_1, a_2$$ such that exactly one of $$(a_1 + a_2) <0$$ or $$(a_1 + 2a_2)<0$$. This is because the product of two positive numbers is positive and the product of two negative numbers is positive but the product of a positive number and a negative number is negative.

Since this problem is under-determined, a useful way to go about solving it is to fix $$a_1$$ at some value and then find $$a_2$$ that satisfies our criteria. Arbitrarily, I chose $$a_1 = -1$$. This gives

$$S = 2(-1 + a_2) (-1 + 2 a_2)$$

Now I decided to make the second factor negative and the third factor positive. This means we need $$a_2 - 1 < 0$$ but $$2a_2 -1 >0$$. Together, these inequalities provide $$\frac{1}{2} < a_2 < 1$$. We can arbitrarily choose any $$a_2$$ in that interval.

Thus one solution among many is $$a_1 = -1, a_2 = \frac{3}{4}$$.

• That helps! Btw, how do I arrive at the eigenvalues mentioned in the original solution?
– db18
Commented Oct 13, 2018 at 18:04
• Compute the kernel matrix using the given inputs. For 2 inputs, the kernel is $2 \times 2$, so you can compute the eigenvalues trivially by hand because the characteristic polynomial is a quadratic, and solving quadratic is easy (en.wikipedia.org/wiki/Quadratic_formula). More information: mathworld.wolfram.com/CharacteristicPolynomial.html
– Sycorax
Commented Oct 13, 2018 at 18:09
• Yes, I'm aware of the quadratic formula and characteristic equation. Maybe I'm missing something obvious in this "Compute the kernel matrix using the given inputs"
– db18
Commented Oct 14, 2018 at 22:58
• You wrote the general expression for computing an element of the kernel matrix in your question. A kernel matrix for 2 vectors has 4 elements. How do you use your expression to populate the 4 elements of the matrix using $x_1, x_2$?
– Sycorax
Commented Oct 14, 2018 at 23:07
• So that gives the Kernel matrix as [2 3;3 4] but this gives the eigenvalues as -0.16 and 6.16
– db18
Commented Oct 14, 2018 at 23:13