# Number of eigenfunctions for kernel

While studying machine learning, I've read the following statement:

The kernel $K(x,y)=(x\cdot y+1)^d$ , for $x, y \in \mathbb{R}^p$, has $M={p+d \choose d}$ eigenfunctions that span the space of polynomials in $\mathbb{R}^p$ of total degree $d$.

I do not understand how does the $M={p+d \choose d}$ come from? What does exactly the degree $d$ mean here?

• @mpiktas Sorry, simultaneous edit :-|
– user88
Apr 21, 2011 at 20:14
• @bit-question, I've latexified your question, but it is clear that definition for $K$ is wrong. What is $(x,y)$? Apr 21, 2011 at 20:15
• @mbq, $(x|y)$ is physics notation for scalar product? Apr 21, 2011 at 20:16
• @mpiktas Rather $\langle x\mid y\rangle$... I thought this is the math one (-;
– user88
Apr 21, 2011 at 20:18
• @bit-question, is this exact citation? Could you please give a reference? Apr 21, 2011 at 20:36

The polynomial kernel $K(x,y) = (x \cdot y + 1)^d$ is easily represented in terms of monomials. The degree $d$ is the maximum degree of the polynomial computed by the kernel and therefore also the maximum degree of any contained monomial.

The problem of determining the number of monomials of degree exactly $d$ in $p$ input variables is the same as the problem of finding the number of combinations to draw $d$ elements from a bin with $p$ different elements. The number of such $d$-combinations is

$$\left(\!\!{d \choose p}\!\!\right) = {d + p - 1 \choose d} = {d + p - 1 \choose p - 1}.$$

However, we need to consider all monomials of degree $k = 0, \ldots, d$. Using $\sum_{j=k}^{n}{j \choose k} = {n+1 \choose k+1}$ we get

$$\sum_{k=0}^{d}{p - 1 + k \choose p - 1} = \sum_{k=(p-1)}^{(p-1)+d}{k \choose p - 1} = {p + d \choose p} = {p + d \choose d}.$$

Addendum: This formula also nicely showcases the power of kernel functions: Just consider the case where $p = 256$ and $d = 2$. The kernel calculates the scalar product of two vectors (representing the scalar in front of each monomial base function) in a space with dimension ${d + p \choose d} = {256 + 2 \choose 2} = 33153$. An explicit scalar product computation thus involves 33153 multiplications and additions, while the kernel needs $p + d - 1 = 257$ multiplications and $p = 256$ additions.

Take a simple example, if $x,z \in \mathbb{R}^2$, and $d=2$, then,

$$(\left< x , z \right> + 1)^2 = (x_1z_1 + x_2z_2 + 1)^2$$ $$= x_1^2z_1^2 + x_2^2z_2^2 + 2x_1z_1x_2z_2 +x_1z_1 + x_2z_2 + 1$$ $$= \left< (x_1^2, x_2^2, \sqrt{2}x_1x_2, x_1, x_2, 1), (z_1^2, z_2^2, \sqrt{2}z_1z_2, z_1, z_2, 1) \right>$$ $$= \left< \phi(\bf{x}), \phi(\bf{z}) \right>$$

where $\phi(\cdot)$ is the feature map, which we can see has 6 eigenfunctions. In this case $p=2$ and $d=2$, so there should be $\left( \begin{array}{c} 4 \\ 2 \end{array} \right) = 6$ eigenfunctions, as predicted. This is trivial but laborious to show for higher dimensions or higher polynomial degree orders.