16
$\begingroup$

How can I prove that pointwise product of two kernel functions is a kernel function?

$\endgroup$
22
$\begingroup$

By point-wise product, I assume you mean that if $k_1(x,y), k_2(x,y)$ are both valid kernel functions, then their product

\begin{align} k_{p}( x, y) = k_1( x, y) k_2(x,y) \end{align}

is also a valid kernel function.

Proving this property is rather straightforward when we invoke Mercer's theorem. Since $k_1, k_2$ are valid kernels, we know (via Mercer) that they must admit an inner product representation. Let $a$ denote the feature vector of $k_1$ and $b$ denote the same for $k_2$.

\begin{align} k_1(x,y) = a(x)^T a(y), \qquad a( z ) = [a_1(z), a_2(z), \ldots a_M(z)] \\ k_2(x,y) = b(x)^T b(y), \qquad b( z ) = [b_1(z), b_2(z), \ldots b_N(z)] \end{align}

So $a$ is a function that produces an $M$-dim vector, and $b$ produces an $N$-dim vector.

Next, we just write the product in terms of $a$ and $b$, and perform some regrouping.

\begin{align} k_{p}(x,y) &= k_1(x,y) k_2(x,y) \\&= \Big( \sum_{m=1}^M a_m(x) a_m(y) \Big) \Big( \sum_{n=1}^N b_n(x) b_n(y) \Big) \\&= \sum_{m=1}^M \sum_{n=1}^N [ a_m(x) b_n(x) ] [a_m(y) b_n(y)] \\&= \sum_{m=1}^M \sum_{n=1}^N c_{mn}( x ) c_{mn}( y ) \\&= c(x)^T c(y) \end{align}

where $c(z)$ is an $M \cdot N$ -dimensional vector, s.t. $c_{mn}(z) = a_m(z) b_n(z)$.

Now, because we can write $k_p(x,y)$ as an inner product using the feature map $c$, we know $k_p$ is a valid kernel (via Mercer's theorem). That's all there is to it.

$\endgroup$
2
  • 2
    $\begingroup$ How do you know that the feature Hilbert space is finite-dimensional? Couldn't it be even non-separable? $\endgroup$ – Andrei Kh Oct 20 '19 at 11:33
  • 1
    $\begingroup$ @ViktorGlombik this is a valid conclusion, but should have a sentence of explanation. $k_p$ being representable as the inner product of two vectors obviously means that properties of the inner product transfer to the kernel $k_p$. The inner product is by definition symmetric and positive semi definite, hence so is $k_p$. $\endgroup$ – Doc Jul 23 '20 at 15:33
4
$\begingroup$

How about the following proof:

enter image description here

Source: UChicago kernel methods lecture, page 5

$\endgroup$
0
$\begingroup$

Assume $K1$ and $K2$ are the kernel matrix of these two kernel $k_1(x,y)$ and $k_2(x,y)$, respectively, and they are PSD. We define $k(x,y) = k_1(x,y)k_2(x,y)$ and want to prove it is also a kernel. This is equivalent to prove its corresponding kernel matrix $K = K1 \circ K2$ is PSD.

  1. $K_3 = K1 \otimes K2$ is a PSD (The kronecker product of two PSD is PSD).
  2. $K$ is a principal submatrix of $K_3$, and therefore is PSD (The principal submatrix of PSD is PSD).
$\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.