Exercise 12.10: Kernels and Power Sets

chapter 12

Since $S$ is finite, we can encode each subset $A\subseteq S$ as a binary string $\varphi (A)=[\mathbb{1}\{s\in A\}{]}_{s\in S}\in \{0,1{\}}^{|S|}$. Hence $k(A,B)=2^{\tilde{k}(A,B)}$ for any two subset $A,B$, where $\tilde{k}(A,B)=⟨\varphi (A),\varphi (B)⟩$ is a valid kernel. We can thus use the Maclaurin series $$\begin{array}{}\text{(1)}& k(A,B)=\sum _{j=0}^{\mathrm{\infty }}\frac{(\log 2{)}^j}{j!}\tilde{k}(A,B{)}^j;\end{array}$$ because $\frac{(\log 2{)}^j}{j!}\ge 0$ and $\tilde{k}(A,B{)}^j$ is a psd kernel for every $j$, $k$ is a pointwise limit of psd kernels, which is itself psd since the cone of psd matrices is closed.