If $A : X' \rightarrow X$ and $k$ is a kernel on X, then $k$' defined by $k'(x,y) = k(A(x), A(y))$ is a kernel on $X'$ - proof help

Question

Studying kernels and I came across this PDF:

I am not a mathematician and I barely understand kernels, but I would like to see the proof for Lemma $4$.

If $A$ : $X' → X$ and $k$ is a kernel on $X$, then $k' $defined by $k'(x,x') = k(A(x), A(x'))$ is a kernel on $X'$.

I'm not sure how to begin to show that $k'$ is a kernel, much less that $k'$ is PSD.

I think for the latter I need to show something like: $$ A^{T} \textbf{K} A \geq 0 => x^{T} \textbf{K} x \geq 0 $$

but I don't understand why $k' = k$.

Answer 1

I don't see lemma 4 in the PDF, but yes, you need to show $k'$ is positive semidefinite and symmetric.

Since $k$ is a valid kernel for all $x \in X$, any function which maps elements $x' \in X'$ to $X$ will induce a natural kernel on $X'$ (the pullback of kernel $k$ under $A$).

To see that $k'$ is symmetric, use that $k$ is a kernel: $$ k'(x',x) := k(A(x'),A(x)) = k(A(x),A(x')) =: k'(x,x') $$ To see that $k'$ is positive semidefinite, use that $k$ is a kernel: $$ k'(x',x) := k(A(x'),A(x)) = k(\tilde{x}', \tilde{x}) \geq 0 \quad \forall \tilde{x}, \tilde{x}' \in X $$