Exercise 12.8: PSD Kernels
(a)
False: Let \(k_1(x, x') = 0\), \(k(x, x') = \langle x, x' \rangle\), and take \(\langle x, x' \rangle = - c\) for some \(c > 0\). Then \begin{align} \begin{bmatrix} (k_1 \wedge k_2) (x, x) & (k_1 \wedge k_2) (x, x’) \newline (k_1 \wedge k_2) (x’, x) & (k_1 \wedge k_2) (x’, x’) \end{bmatrix} \begin{bmatrix} 1 / \sqrt{2} \newline 1 / \sqrt{2} \end{bmatrix} = - c \begin{bmatrix} 1 / \sqrt{2} \newline 1 / \sqrt{2} \end{bmatrix} \, , \end{align} meaning the matrix is not positive semidefinite.
(b)
True: For any \(N \in \N\) and \(X = \{x_1, \ldots, x_N\} \in \X^N\). Then \begin{align} k(X, X) = [f(X) f(X)^\top] \odot [n_f(X) n_f(X)^\top] \, , \end{align} where \(k(X, X) \in \R^{N \times N}\), \(f(X) = \{ f(x_1), \ldots , f(x_N) \}\), and \(n_f(X) = \{ 1 / \| f(x_1) \| , \ldots , 1 / \| f(x_N) \| \}\). Clearly both \(f(X) f(X)^\top\) and \(n_f(X) n_f(X)^\top\) are positive semidefinite. Hence \(k(X, X)\) is psd by the Schur product theorem.
Notes
- In (b), we are assuming \(\| f(x) \| > 0\) for all \(x \in \X\) as otherwise we would have to be dealing with the extended real axis for the domain. The book does not comment on this.