Prove that multiplication with positive semidefinite matrix is a kernel

Question

Let $A \in \mathbb{R}^{d \times d}$ be a symmetric and positive semi-definite matrix. Prove that

$$ k(\textbf{x}, \textbf{x}') = \textbf{x}^T A \textbf{x}' $$

is a kernel.

My first thought when I saw this question was that $A$ can be interpreted to be the kernel matrix of $k$ and that's it. But $A$ and the kernel matrix of $k$ can be completely different, making this idea not work.

This can be proven either by showing that the kernel matrix of $k$ is positive semidefinite or by utilizing a kernel feature map $\phi$. I assume that the first approach makes more sense here, but I don't see how this can be proven just yet.

How can it be proven that $k$ is a kernel?

Answer 1

Since $A$ is symmetric and PSD, it can be written as $$A=Q\Lambda Q^T=(Q\Lambda^{1/2})(Q\Lambda^{1/2})^T=M^TM$$ where $M=(Q\Lambda^{1/2})^T$. So, the kernel can be expressed as $$k(x,x')=x^TM^TMx'=(Mx)^T(Mx')=<Mx,Mx'>$$ So, the corresponding transformation is $\phi(x)=Mx$, and $k$ is a kernel.