For any valid psd kernel $k : \mathcal X \times \mathcal X \to \mathbb R$, there exists a feature map $\varphi : \mathcal X \to \mathcal H$ such that $k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$. The space $\mathcal H$ and embedding $\varphi$ in fact need not be unique, but there is an important unique $\mathcal H$ known as the reproducing kernel Hilbert space (RKHS).

The RKHS is discussed by: Steinwart, Hush and Scovel, An Explicit Description of the Reproducing Kernel Hilbert Spaces of Gaussian RBF Kernels, IEEE Transactions on Information Theory 2006 (doi, free citeseer pdf).

It's somewhat complicated, and they need to analyze it via the extension of the Gaussian kernel to complex inputs and outputs, but it boils down to this: define $e_n : \mathbb R \to \mathbb R$ as $$ e_n(x) := \sqrt{\frac{(2 \sigma^2)^n}{n!}} x^n e^{-\sigma^2 x^2} $$ and, for a tuple $\nu = (\nu_1, \cdots, \nu_d) \in \mathbb N_0^d$, its tensor product $e_\nu : \mathbb R^d \to \mathbb R$ as $$ e_\nu(x) = e_{\nu_1}(x_1) \cdots e_{\nu_d}(x_d) .$$ Then their Proposition 3.6 says that any function $f \in \mathcal H_\sigma$, the RKHS for a Gaussian kernel of bandwidth $\sigma > 0$, can be written as $$ f(x) = \sum_{\nu \in \mathbb N_0^d} b_\nu e_\nu(x) \qquad \lVert f \rVert_{\mathcal H_\sigma(X)}^2 = \sum_{\nu \in \mathbb N_0^d} b_\nu^2 .$$

We can think of $\mathcal H_\sigma$ as being essentially the space of square-summable coefficients $(b_\nu)_{\nu \in \mathbb N_0^d}$.

The question remains, though: what is the the sequence $b_\nu$ for the function $\phi(x)$? The paper doesn't seem to directly answer this question (unless I'm missing it as an obvious implication somewhere).

The do also give a more straightforward embedding into $L_2(\mathbb R^d)$, the Hilbert space of square-integrable functions from $\mathbb R^d \to \mathbb R$: $$ \Phi(x) = \frac{(2 \sigma)^{\frac{d}{2}}}{\pi^{\frac{d}{4}}} e^{- 2 \sigma^2 \lVert x - \cdot \rVert_2^2} .$$ Note that $\Phi(x)$ is itself a function from $\mathbb R^d$ to $\mathbb R$. It's basically the density of a $d$-dimensional Gaussian with mean $x$ and covariance $\frac{1}{4 \sigma^2} I$; only the normalizing constant is different. Thus when we take $$\langle \Phi(x), \Phi(y) \rangle_{L_2} = \int [\Phi(x)](t) \; [\Phi(y)](t) \,\mathrm d t ,$$ we're taking the product of Gaussian density functions, which is itself a certain constant times a Gaussian density functions. When you do that integral by $t$, then, the constant that falls out ends up being exactly $k(x, y)$.

These are not the only embeddings that work.

Another is based on the Fourier transform, which the celebrated paper of Rahimi and Recht (Random Features for Large-Scale Kernel Machines, NIPS 2007) approximates to great effect.

You can also do it using Taylor series: effectively the infinite version of Cotter, Keshet, and Srebro, Explicit Approximations of the Gaussian Kernel, arXiv:1109.4603.

For any valid psd kernel $k : \mathcal X \times \mathcal X \to \mathbb R$, there exists a feature map $\varphi : \mathcal X \to \mathcal H$ such that $k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$. The space $\mathcal H$ and embedding $\varphi$ in fact need not be unique, but there is an important unique $\mathcal H$ known as the reproducing kernel Hilbert space (RKHS).

The RKHS is discussed by: Steinwart, Hush and Scovel, An Explicit Description of the Reproducing Kernel Hilbert Spaces of Gaussian RBF Kernels, IEEE Transactions on Information Theory 2006 (doi, free citeseer pdf).

It's somewhat complicated, and they need to analyze it via the extension of the Gaussian kernel to complex inputs and outputs, but it boils down to this: define $e_n : \mathbb R \to \mathbb R$ as $$ e_n(x) := \sqrt{\frac{(2 \sigma^2)^n}{n!}} x^n e^{-\sigma^2 x^2} $$ and, for a tuple $\nu = (\nu_1, \cdots, \nu_d) \in \mathbb N_0^d$, its tensor product $e_\nu : \mathbb R^d \to \mathbb R$ as $$ e_\nu(x) = e_{\nu_1}(x_1) \cdots e_{\nu_d}(x_d) .$$ Then their Proposition 3.6 says that any function $f \in \mathcal H_\sigma$, the RKHS for a Gaussian kernel of bandwidth $\sigma > 0$, can be written as $$ f(x) = \sum_{\nu \in \mathbb N_0^d} b_\nu e_\nu(x) \qquad \lVert f \rVert_{\mathcal H_\sigma(X)}^2 = \sum_{\nu \in \mathbb N_0^d} b_\nu^2 .$$

We can think of $\mathcal H_\sigma$ as being essentially the space of square-summable coefficients $(b_\nu)_{\nu \in \mathbb N_0^d}$.

The question remains, though: what is the the sequence $b_\nu$ for the function $\phi(x)$? The paper doesn't seem to directly answer this question (unless I'm missing it as an obvious implication somewhere).

The do also give a more straightforward embedding into $L_2(\mathbb R^d)$, the Hilbert space of square-integrable functions from $\mathbb R^d \to \mathbb R$: $$ \Phi(x) = \frac{(2 \sigma)^{\frac{d}{2}}}{\pi^{\frac{d}{4}}} e^{- 2 \sigma^2 \lVert x - \cdot \rVert_2^2} .$$ Note that $\Phi(x)$ is itself a function from $\mathbb R^d$ to $\mathbb R$. It's basically the density of a $d$-dimensional Gaussian with mean $x$ and covariance $\frac{1}{4 \sigma^2} I$; only the normalizing constant is different. Thus when we take $$\langle \Phi(x), \Phi(y) \rangle_{L_2} = \int [\Phi(x)](t) \; [\Phi(y)](t) \,\mathrm d t ,$$ we're taking the product of Gaussian density functions, which is itself a certain constant times a Gaussian density functions. When you do that integral by $t$, then, the constant that falls out ends up being exactly $k(x, y)$.

These are not the only embeddings that work.

Another is based on the Fourier transform, which the celebrated paper of Rahimi and Recht (Random Features for Large-Scale Kernel Machines, NIPS 2007) approximates to great effect.

You can also do it using Taylor series: effectively the infinite version of Cotter, Keshet, and Srebro, Explicit Approximations of the Gaussian Kernel, arXiv:1109.4603.

For any valid psd kernel $k : \mathcal X \times \mathcal X \to \mathbb R$, there exists a feature map $\varphi : \mathcal X \to \mathcal H$ such that $k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$. The space $\mathcal H$ and embedding $\varphi$ in fact need not be unique, but there is an important unique pair $(\mathcal H, \varphi)$ known as the reproducing kernel Hilbert space (RKHS).

The RKHS is discussed by: Steinwart, Hush and Scovel, An Explicit Description of the Reproducing Kernel Hilbert Spaces of Gaussian RBF Kernels, IEEE Transactions on Information Theory 2006 (doi, free citeseer pdf).

It's somewhat complicated, but it boils down to this: define $e_n : \mathbb C \to \mathbb C$ as $$ e_n(z) := \sqrt{\frac{(2 \sigma^2)^n}{n!}} z^n e^{-\sigma^2 z^2} .$$

Let $n : \mathbb{N}_0 \to \mathbb{N}_0^d$ be a sequence ranging over all $d$-tuples of nonnegative integers; if $d = 3$, perhaps $n(0) = (0, 0, 0)$, $n(1) = (0, 0, 1)$, $n(2) = (0, 1, 1)$, and so on. Denote the $j$th component of the $i$th tuple by $n_{ij}$.

Then the $i$th component of $\varphi(x)$ is $\prod_{j=1}^d e_{n_{ij}}(x_j)$. So $\varphi$ maps vectors in $\mathbb R^d$ to infinite-dimensional complex vectors.

The catch to this is that we further have to define norms for these infinite-dimensional complex vectors in a special way; see the paper for details.

Steinwart et al. also give a more straightforward (to my thinking) embedding into $L_2(\mathbb R^d)$, the Hilbert space of square-integrable functions from $\mathbb R^d \to \mathbb R$: $$ \Phi_\sigma(x) = \frac{(2 \sigma)^{\frac{d}{2}}}{\pi^{\frac{d}{4}}} e^{- 2 \sigma^2 \lVert x - \cdot \rVert_2^2} .$$ Note that $\Phi_\sigma(x)$ is itself a function from $\mathbb R^d$ to $\mathbb R$. It's basically the density of a $d$-dimensional Gaussian with mean $x$ and covariance $\frac{1}{4 \sigma^2} I$; only the normalizing constant is different. Thus when we take $$\langle \Phi(x), \Phi(y) \rangle_{L_2} = \int [\Phi(x)](t) \; [\Phi(y)](t) \,\mathrm d t ,$$ we're taking the product of Gaussian density functions, which is itself a certain constant times a Gaussian density functions. When you do that integral by $t$, then, the constant that falls out ends up being exactly $k(x, y)$.

These are not the only embeddings that work.

Another is based on the Fourier transform, which the celebrated paper of Rahimi and Recht (Random Features for Large-Scale Kernel Machines, NIPS 2007) approximates to great effect.

You can also do it using Taylor series: effectively the infinite version of Cotter, Keshet, and Srebro, Explicit Approximations of the Gaussian Kernel, arXiv:1109.4603.

For any valid psd kernel $k : \mathcal X \times \mathcal X \to \mathbb R$, there exists a feature map $\varphi : \mathcal X \to \mathcal H$ such that $k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$. The space $\mathcal H$ and embedding $\varphi$ in fact need not be unique, but there is an important unique $\mathcal H$ known as the reproducing kernel Hilbert space (RKHS).

The RKHS is discussed by: Steinwart, Hush and Scovel, An Explicit Description of the Reproducing Kernel Hilbert Spaces of Gaussian RBF Kernels, IEEE Transactions on Information Theory 2006 (doi, free citeseer pdf).

It's somewhat complicated, and they need to analyze it via the extension of the Gaussian kernel to complex inputs and outputs, but it boils down to this: define $e_n : \mathbb R \to \mathbb R$ as $$ e_n(x) := \sqrt{\frac{(2 \sigma^2)^n}{n!}} x^n e^{-\sigma^2 x^2} $$ and, for a tuple $\nu = (\nu_1, \cdots, \nu_d) \in \mathbb N_0^d$, its tensor product $e_\nu : \mathbb R^d \to \mathbb R$ as $$ e_\nu(x) = e_{\nu_1}(x_1) \cdots e_{\nu_d}(x_d) .$$ Then their Proposition 3.6 says that any function $f \in \mathcal H_\sigma$, the RKHS for a Gaussian kernel of bandwidth $\sigma > 0$, can be written as $$ f(x) = \sum_{\nu \in \mathbb N_0^d} b_\nu e_\nu(x) \qquad \lVert f \rVert_{\mathcal H_\sigma(X)}^2 = \sum_{\nu \in \mathbb N_0^d} b_\nu^2 .$$

We can think of $\mathcal H_\sigma$ as being essentially the space of square-summable coefficients $(b_\nu)_{\nu \in \mathbb N_0^d}$.

The question remains, though: what is the the sequence $b_\nu$ for the function $\phi(x)$? The paper doesn't seem to directly answer this question (unless I'm missing it as an obvious implication somewhere).

The do also give a more straightforward embedding into $L_2(\mathbb R^d)$, the Hilbert space of square-integrable functions from $\mathbb R^d \to \mathbb R$: $$ \Phi(x) = \frac{(2 \sigma)^{\frac{d}{2}}}{\pi^{\frac{d}{4}}} e^{- 2 \sigma^2 \lVert x - \cdot \rVert_2^2} .$$ Note that $\Phi(x)$ is itself a function from $\mathbb R^d$ to $\mathbb R$. It's basically the density of a $d$-dimensional Gaussian with mean $x$ and covariance $\frac{1}{4 \sigma^2} I$; only the normalizing constant is different. Thus when we take $$\langle \Phi(x), \Phi(y) \rangle_{L_2} = \int [\Phi(x)](t) \; [\Phi(y)](t) \,\mathrm d t ,$$ we're taking the product of Gaussian density functions, which is itself a certain constant times a Gaussian density functions. When you do that integral by $t$, then, the constant that falls out ends up being exactly $k(x, y)$.

These are not the only embeddings that work.

Another is based on the Fourier transform, which the celebrated paper of Rahimi and Recht (Random Features for Large-Scale Kernel Machines, NIPS 2007) approximates to great effect.

You can also do it using Taylor series: effectively the infinite version of Cotter, Keshet, and Srebro, Explicit Approximations of the Gaussian Kernel, arXiv:1109.4603.