In this problem, we consider constructing new kernels by combining existing kernels. Recall that for some function k(x,z) to be a kernel, we need to be able to write it as a dot product of vectors in some high-dimensional feature space defined by :

k(x, z) = (x)(z)

Mercers theorem gives a necessary and sufficient condition for a function k to be a kernel function: its corresponding kernel matrix K has to be symmetric and positive semidefinite.

Suppose that k1(x,z) and k2(x,z) are two valid kernels. For each of the cases below, state whether k is also a valid kernel. If it is, prove it. If it is not, give a counterexample. You can use either Mercers theorem, or the definition of a kernel as needed to prove it.

(a) [10 points] k(x, z) = k1(x, z)k2(x, z) (b) [10 points] k(x, z) = f1(x)f1(z) + f2(x)f2(z), where f1, f2 : Rn R are a real-valued functions

(c) [10 points] k(x,z) = k1(x,z) , where k1(x,x) > 0 for any x.