Regularized linear vs. RKHS-regression I'm studying the difference between regularization in RKHS regression and linear regression, but I have a hard time grasping the crucial difference between the two.
Given input-output pairs $(x_i,y_i)$, I want to estimate a function $f(\cdot)$ as follows
\begin{equation}f(x)\approx u(x)=\sum_{i=1}^m \alpha_i K(x,x_i),\end{equation}
where $K(\cdot,\cdot)$ is a kernel function. The coefficients $\alpha_m$ can either be found by  solving
\begin{equation}
 {\displaystyle \min _{\alpha\in R^{n}}{\frac {1}{n}}\|Y-K\alpha\|_{R^{n}}^{2}+\lambda \alpha^{T}K\alpha},\end{equation}
where, with some abuse of notation, the $i,j$'th entry of the kernel matrix $K$ is ${\displaystyle K(x_{i},x_{j})} $. This gives
\begin{equation}
\alpha^*=(K+\lambda nI)^{-1}Y.
\end{equation}
Alternatively, we could treat the problem as a normal ridge regression/linear regression problem:
\begin{equation}
 {\displaystyle \min _{\alpha\in R^{n}}{\frac {1}{n}}\|Y-K\alpha\|_{R^{n}}^{2}+\lambda \alpha^{T}\alpha},\end{equation}
with solution
\begin{equation}
{\alpha^*=(K^{T}K +\lambda nI)^{-1}K^{T}Y}.
\end{equation}
What would be the crucial difference between these two approaches and their solutions?
 A: Both of the penalties can be thought of as arising from the linear regression setting in a Bayesian framework with predictor matrix $K$ and a Gaussian prior over the vector $\alpha$, centered at zero with prior variance $V$. 
In the ridge regression case $V = n^{-1}\lambda^{-1}I$ and in the other case $V = n^{-1}\lambda^{-1}K^{-1}$ (as a kernel matrix $K$ is symmetric and PSD; I'm also assuming it is invertible). This follows just by equating terms; the posterior mean has the form $(K^tK + V^{-1})^{-1}K^tY$. Plugging in $V = n^{-1}\lambda^{-1}K^{-1}$ gives $$(K^tK + n\lambda K)^{-1}K^tY = (K^t + n\lambda I)^{-1}K^{-1}K^tY = (K + n\lambda I)^{-1}Y.$$
Anyway, this is all just definitions, but the perspective might be intuition-boosting: the RKHS version stipulates explicitly that the prior over alpha has higher precision (more regularization) along directions of high variation as defined by the kernel function. 
A: To appreciate the difference, it is helpful to consider the case that $K$ is invertible. For small $\lambda$ the solution should then be close to $\alpha^\ast=K^{-1}Y\equiv\alpha_0$.
For the first solution, the RKHS regularization, one finds
$$\alpha^\ast=\alpha_0 +n\lambda K^{-1}\alpha_0 + {\cal O}(\lambda^2).$$
For the second solution, instead
$$\alpha^\ast=\alpha_0 +n\lambda (K^TK)^{-1}\alpha_0 + {\cal O}(\lambda^2).$$
When the smallest eigenvalues of $K$ become of order $\epsilon\rightarrow 0$, the deviation of $\alpha^\ast$ from $\alpha_0$ in the first case is of order $n\lambda/\epsilon$, while the deviation in the second case is larger, of order $n\lambda/\epsilon^2$. This is why the RKHS regularization is preferrable.
A: The difference is of course that the two penalty terms, $\alpha^{T}K\alpha$ and $\alpha^{T}\alpha$, penalize rather differently. Suppose that $n=m$ is very large and $K(x,y)=K(x-y)$ for some (say even) function $K$ (typical cases should be similar to this). 
Then we can consider an infinite-dimensional approximation of this finite-dimensional setting. Let us see how the kernel $K$ acts on the harmonic $e_k$ of frequency $k\in\mathbb R$ given by the formula $e_k(x):=e^{ikx}$ for real $x$: 
\begin{equation}
 (Ke_k)(x)=\int_{-A}^A K(x-y)e^{iky}dy=\int_{x-A}^{x+A} K(u)e^{ik(x-u)}du\approx\lambda_k e_k(x), 
\end{equation}
where $A\in(0,\infty)$ is very large and 
\begin{equation}
 \lambda_k:=\int_{-\infty}^\infty K(u)e^{-iku}du, 
\end{equation}
so that $e_k$ is an approximate eigenvector of $K$ with approximate eigenvalue $\lambda_k$. If $|k|\to\infty$ then, by an appropriate version of the Riemann--Lebesgue lemma, $\lambda_k$ goes to $0$; this convergence is the faster, the smoother $K$ is. So, the RKHS penalizer is lenient with respect to high-frequency harmonics $e_k$, with large $|k|$ -- that is, $e_k^T Ke_k=(Ke_k,e_k)\approx\lambda_k(e_k,e_k)=A\lambda_k$ with $\lambda_k$ small. Accordingly, with the total size $\|\alpha\|_2$ of the minimizing mixture $\alpha$ of harmonics $e_k$ fixed, the RKHS penalty term penalizes mainly the low-frequency constituent harmonics $e_k$ of $\alpha$, with $|k|$ comparatively small. This behavior may result in better catching (by the minimizer) fine, high-frequency features of the unknown, estimated function $f$. However, such behavior may be not so desirable when there is prior knowledge that the true $f$ is rather smooth (whereas some constituent smooth, low-frequency harmonics got partially penalized out). 
The ridge penalty term $\alpha^{T}\alpha=(\alpha,\alpha)$ can actually be considered a special case of $\alpha^{T}K\alpha=(K\alpha,\alpha)$ with $K(x-y)=\delta(x-y)$, the delta-function kernel, which is of course very non-smooth. This latter kernel treats all the harmonic frequencies whatsoever absolutely equally: $\delta e_k=e_k$ for all $k$; it is the ultimate "equal opportunity" penalizer, in contrast with the smooth-kernel one. 
One should also note that, if $K$ is smooth, the estimate $K\alpha$ of $f$ will to an extent suppress the constituent high-frequency harmonics of $\alpha$, whether $\alpha$ is the RKHS minimizer or the ridge one. However, it should be clear from the above discussion that the overall suppression of the high-frequency harmonics will be relatively less in the RKHS case. 
