Exercise 12.10: Kernels and Power Sets
Since \(S\) is finite, we can encode each subset \(A \subseteq S\) as a binary string \(\phi(A) = [\ind \{ 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) = \langle \phi(A), \phi(B) \rangle\) is a valid kernel. We can thus use the Maclaurin series \begin{align} k(A, B) = \sum_{j=0}^\infty \frac{(\log 2)^j}{j !} \tilde{k} (A, B)^j \, ; \end{align} because \(\frac{(\log 2)^j}{j !} \geq 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.