Linear combination of two kernel functions

How can I prove that linear combination of two kernel functions is also a kernel function?

k_{p}( x, y) = a_1k_1( x, y) + a_2k_2(x,y)

given $k_1(,)$ and $k_2(,)$ are valid kernel functions.

In general to prove any such results involving dot product , cascading.. etc. , what methodology can be followd to prove RHS is a kernel function given k’s in LHS all are kernel?


A necessary and sufficient condition for a function $\kappa(\cdot,\cdot)$ to be expressible as an inner product in some feature space $\mathcal{F}$ is a weak form of Mercer’s condition, namely that:

\int_\mathbf{x} \int_\mathbf{y} \kappa(\mathbf{x},\mathbf{y})g(\mathbf{x})g(\mathbf{y})d\mathbf{x}d\mathbf{y} \geq 0,
for all square, integrable functions $g(\cdot)$ [1,2].

In your case, this reduces to the following:
&\int_\mathbf{x} \int_\mathbf{y}
\big(a_1\kappa_1(\mathbf{x},\mathbf{y}) + a_2 \kappa_2(\mathbf{x},\mathbf{y})\big)g(\mathbf{x})g(\mathbf{y})d\mathbf{x}d\mathbf{y} \\
&= a_1 \underbrace{\int_\mathbf{x} \int_\mathbf{y} \kappa_1(\mathbf{x},\mathbf{y})g(\mathbf{x})g(\mathbf{y})d\mathbf{x}d\mathbf{y}}_{\geq 0} + a_2 \underbrace{\int_\mathbf{x} \int_\mathbf{y}\kappa_2(\mathbf{x},\mathbf{y})g(\mathbf{x})g(\mathbf{y})d\mathbf{x}d\mathbf{y}}_{\geq 0} \geq 0.
Since $\kappa_1(\cdot,\cdot)$ and $\kappa_2(\cdot,\cdot)$ are given to be kernel functions, their integrals both satisfy Mercer’s condition. Finally, if $a_1 \geq 0$ and $a_2 \geq 0$, then the overall integral is guaranteed to satisfy it too. $\blacksquare$

Note that, as @Dougal correctly pointed out, it is still possible to get a valid kernel function with negative $a_1$ or $a_2$ (not both), but that depends on several factors.

[1] Vladimir N. Vapnik. Statistical learning theory. Wiley, 1 edition, September 1998.

[2] Richard Courant and David Hilbert. Methods of Mathematical Physics, volume 1. Interscience Publishers, Inc.,
New York, NY, 1953

Source : Link , Question Author : tusharfloyd , Answer Author : Marc Claesen

Leave a Comment