Kernel methods - How do the infinite dimensions arise? I'm going through the Kernel chapter from Kevin Murphy's Machine Learning book and he talks about the importance of positive definite or Mercer kernels:

My question comes from the last sentence: What makes φ depend on the eigen functions of κ, and how does that make $D$ be a potentially infinite dimensional space?
I think I'm missing something critical for the understanding of kernels and SVMs.
 A: A positive definite symmetric matrix $A$ can be written as:
$$A=\sum_{k=1}^n\lambda_k e_ke^T_k,$$
where $Ae_k=\lambda_ke_k$ and $e_k$ are the normalized eigenvectors of $A$. This is completely equivalent to the eigendecomposition form: $A=U\Sigma U^T$, where $U$ is the unitary matrix whose columns are $e_j$. In particular, $A$ can also be thought of as a function function from $\mathbb{R}^2$ to $\mathbb{R}$:
$$[A]_{ij}:=A(i,j)=\sum_{k=1}^n\lambda_ke_{ki}e_{kj}=\phi^T(i)\phi(j),$$
where $e_{kj}:=[e_k]_j$, i.e. the j'th component of eigenvector $e_k$, and $\phi^T(i):=(\sqrt{\lambda_1}e_{1i},\sqrt{\lambda_2}e_{2i},\cdots,\sqrt{\lambda_n}e_{ni})$. Finally, when we act $A$ on a vector $x$, we write 
$$[Ax]_{i}=(Ax)(i):=\sum_{k=1}^nA(i,k)x_k.$$
A positive definite, symmetric kernel $\kappa(s,s')$ is a function from $\mathcal{X}^2$ to  $\mathbb{R}$. You can think of it as an infinite matrix where indices are continuous instead of just discrete. Thus kernels act on vectors which are now functions. Thus instead of a vector $x=x(i)$ with components $x_i$ ($i=1,2,\cdots,n$), we write $x(s)$, where $s$ is continuous, and therefore $x$ is a function of $s$. There are technical restrictions on what kind of function $x$ can be, which you can learn about if you lookup $L^2$ spaces, specifically: $\int_{-\infty}^\infty |x(s)|^2ds<\infty$. 
A natural definition for defining the action of $\kappa$ on $x$ is through an integral over the continuum of indices, as opposed to the usual discrete sum for matrices:
$$\kappa x=(\kappa x)(s):=\int_{-\infty}^\infty \kappa(s,s')x(s')ds'.$$
Also just like in the discrete case, $\kappa$ has eigenfunctions $e_j=e_j(s)$:
$$(\kappa e_j)(s)=\int_{-\infty}^\infty \kappa(s,s')e(s')ds'=\lambda_j e_j(s).$$
The fact that there are infinitely many eigenfunctions for $\kappa$ comes from the fact that the space of functions on which $\kappa$ acts on is infinite dimensional. Again, a very low brown way of seeing this is to realize that $x=x(s)$ can be thought of as a vector with a continuum of indices. Through the abstract nonsense of Hilbert Schmidt operator theory, one can show (somewhat nontrivially) that if $\kappa$ is analogous to a positive definite matrix, then it possesses a discrete, possibly infinite set of eigenvectors and non-negative eigenvalues, which allows us to write the analog:
$$\kappa(s,s')=\sum_{k=1}^\infty \lambda_j e_j(s)e_j(s')=\phi(s)^T\phi(s'),$$
where $\phi^T(s):=(\sqrt{\lambda_1}e_1(s),\sqrt{\lambda_2}e_2(s),\cdots)$. Notice the dots signify this could potentially be an infinitely long vector.
