# Why is the regularization penality equal to $\langle c , Kc \rangle_{R^n}$ when using the kernel trick in Tikhonov regularization?

This might be a stupid question but why is it that when we try to solve:

$$\min_{f \in \mathcal H} \frac{1}{n} \sum^n_{i=1} L(f(x_i),y_i) + \lambda \|f \|^2_{\mathcal H}$$

in a RKHS (Reproducing Kernel Hilbert space) that the penalty is equivalently expressed as:

$$\|f \|^2_{\mathcal H} = \langle c , Kc \rangle_{R^n}$$

in particular when using the linear function $f(x) = \langle w_i, x_i \rangle_{R^d}$ its clear that the norm $\|f \|^2_{ \mathcal H} = \| w \|^2_2$. However, why does it become $\|f \|^2_{\mathcal H} = \sum^n_{i,j = 1} c_i c_j K(x_i, x_j)$?

Note that I accept the Representer theorem as true, i.e. that $\mathcal H$ is effectively equal to $\hat{\mathcal H} = \{ f \mid f( \cdot) = \sum^n_{i=1} c_i K(x_i, \cdot) \}$ (i.e. we only use function that use the training set points from the RKHS). However, I don't understand how $\langle c , Kc \rangle_{R^n}$ is derived, or from which inner product it came from. Or essentially, my intuition from the linear case to the kernel case seems confused, because in the linear case we don't have the penalty term something involving x. In other words, analogously I would have expected the penalty when $f(x) = \langle w_i, x_i \rangle_{R^d}$ (linear case) to be something like:

$$\|f \|^2_{\mathcal H} = \langle c , Xc \rangle_{R^n} = \sum^n_{i,j = 1} c_i c_j \langle x_i, x_j \rangle_{R^d}$$

but clearly its not and this product $\langle x_i, x_j \rangle_{R^d}$ seems to have gone missing for some reason. i.e. why in the linear case is the norm not $\langle c, XX^T c \rangle$. What happened to $XX^T$?

If we call $K_X = K(x,\cdot)$, we can write $f(x) = K_xc$. Then the functional norm $$||f||^2 = \sum_{i,j} c_i c_j K(x_i,x_j)$$

since $\langle K_x,K_{x'} \rangle = K(x,x')$

If you want to be sloppy but quicker by using the kernel trick, since we can write $w = X^Tc$, then $\langle w,w \rangle$ = $\langle X^Tc,X^Tc \rangle = \langle c,XX^Tc \rangle = \langle c,Kc \rangle$

• I really like your "sloppy trick"! Its very intuitive and succinct. Definitively deserves an upvote (+1). However, its still not clear to me what happened to $XX^T$ in: $$\langle c, XX^T c \rangle$$ in the linear case. Oct 27, 2016 at 23:55

The question is why:

$$\|f \|^2_{\mathcal H} = \langle c , Kc \rangle_{R^n}$$

I will be very thorough.

The original space $\mathcal H$ is an RKHS which means that it has an norm induced by its inner product:

$$\| f \|^2_{\mathcal H} = \langle f, f \rangle_{\mathcal H}$$

by the representer theorem we know:

$$\min_{f \in \mathcal H} \frac{1}{n} \sum^n_{i=1} L(f(x_i),y_i) + \lambda \|f \|^2_{\mathcal H} = \min_{f \in \mathcal{ \hat{H} }} \frac{1}{n} \sum^n_{i=1} L(f(x_i),y_i) + \lambda \|f \|^2_{\mathcal H}$$

therefore we only need to consider functions in $\mathcal{ \hat{H} }$. This means that we only care about function that depend on the data and have form $f(\cdot) = \sum^n_{i=1} c_i K(x_i, \cdot) = f = \sum^n_{i=1}c_i K_{x_i}$. Therefore since we are only considering functions of that form we can plug this in the definition of the norm and we get:

$$\| f \|^2_{\mathcal H} = \langle f, f \rangle_{\mathcal H} = \langle \sum^n_{i=1}c_i K_{x_i}, \sum^n_{i=1}c_i K_{x_i} \rangle_{\mathcal H}$$

recall inner products are linear function (i.e. $\langle f + g, h \rangle_{\mathcal H} = \langle f, h \rangle_{\mathcal H} + \langle g, h \rangle_{\mathcal H}$ or similarly $f(\sum_j x_j, \cdot) = \sum_j f(x_j, \cdot)$). Thus we can apply the function $\langle \cdot, \cdot \rangle$ to each argument (i.e. to each function $K_{x_i}$ individually):

$$\langle \sum^n_{i=1}c_i K_{x_i}, \sum^n_{i=1}c_i K_{x_i} \rangle_{\mathcal H} = \sum^n_{i=1}c_i \langle K_{x_i}, \sum^n_{i=1}c_i K_{x_i} \rangle_{\mathcal H}$$

and again (apply linearity):

$$\sum^n_{i=1}c_i \langle K_{x_i}, \sum^n_{i=1}c_i K_{x_i} \rangle_{\mathcal H} = \sum^n_{i=1} \sum^n_{j=1}c_i c_j \langle K_{x_i}, K_{x_j} \rangle_{\mathcal H}$$

now here is the interesting part where we use the fact we are in a RKHS. Recall an RKHS has the so called "reproducing property". i.e. its continuous evaluation functionals lead it to have the remarkably property:

$$\langle f, K_{x} \rangle_{\mathcal H} = f(x)$$

whenever $f$ and $K_x$ are in the RKHS. In this case it happens that $K_{x_i} = K(x_i, \cdot) \in \mathcal H$. Which means we can use the reproducing property:

$$\langle f, K_{x_i} \rangle_{\mathcal H} = f(x_i)$$

Thus using the reproducing property (what people call the "kernel trick", i.e. we don't need explicit feature maps, just the inner products in this case $K(x_i, x_j)$) we get:

$$\langle K_{x_i}, K_{x_j} \rangle_{\mathcal H} = K_{x_i}(x_j) = K(x_i, x_j)$$

Now its not hard to see that you can organize the $K(x_i, x_i)$ into a matrix and you get:

$$\sum^n_{i=1} \sum^n_{j=1}c_i c_j \langle K_{x_i}, K_{x_j} \rangle_{\mathcal H} = \langle c, Kx \rangle_{R^n} = c^T K c$$

or you can just recall from linear algebra or some other course (maybe optimization) that $$\sum^n_{i=1} \sum^n_{j=1}c_i c_j \langle K_{x_i}, K_{x_j} \rangle_{\mathcal H}$$ is simply a quadratic form and can be expressed as $c^T K c$.

The important bit to notice about this proof is that we started off with an infinite dimensional space and we ended up being to compute its norm in a finite dimensional world! Geesh, thanks representer theorem! ;)

Notice that there is one last point I don't know how to answer and why the linear case does not have that inner product. If someone else can clarify that last bit this question is essentially done! :)