9.5.4 Spectral Kernel The spectral kernel is a classical kernel for classifying “words” from a finite alphabet A . For x 2 S

nqA n and s 2 A q, we set Ns(x) = number of occurence of s in x:

The spectral kernel is then defined by k(x;y) = å

s2A q Ns(x)Ns(y)

for all x;y 2 S

nqA n. It counts the number of common sequences of length q in x and y.

1. Prove that k is a positive definite kernel on S

nqA n.

2. Check that the computational complexity for computing k(x;y) is at most of order

`(x)+`(y), where `(x) is the length of x.