Prediciting an output with (kernelized) ridge regression The optimal weight w* for ridge regression is ($\lambda$ is a positive scalar):
$$w^* = (XX^T+\lambda I_n)^{-1}Xy$$
I want to predict the output for a new datapoint $x_i$, whereby $w^*$ is already given - how could that be calculated? I would use the above equation to reformulate:
$$y_i = w^T*x_i$$
to
$$y_{test} = \sum_i y_i x_i^T* (x_ix_i^T+\lambda)^{-1}x_{test}$$
but that does not seem to make any sense since now I get $y$ on both sides?
 A: I think this addresses what you're asking, but correct me if I'm wrong.
In normal ridge regression, we have a $p \times n$ data matrix $X$ corresponding to the $n \times 1$ vector of labels $y$. If we don't want to use an explicit constant term, we fit a model with
$$
w = (X X^T + \lambda I)^{-1} X y
$$
and then make predictions with
$$
y_\text{test} = w^T x_\text{test}
.$$
Combining the two steps, this is
$$
y_\text{test} = y^T X^T (X X^T + \lambda I)^{-1} x_\text{test}
\tag{*}
.$$

In kernelized ridge regression, we want to implicitly do some feature transformation of the input points to a possibly infinite-dimensional Hilbert space. So we don't want to do anything with $X$ directly, since it might be infinitely big; instead, we want to only work with the $n \times n$ matrix of kernel values, $K = X^T X$.
To do that, we can use the following identity:
$$
\left( X X^T + \lambda I \right)^{-1} X
 = X \left( X^T X + \lambda I \right)^{-1}
\tag{**}
$$
which you can see is true by considering:
\begin{align}
     \left( X X^T + \lambda I \right) X \left( X^T X + \lambda I \right)^{-1}
  &= \left( X X^T X + \lambda X \right) \left( X^T X + \lambda I \right)^{-1}
\\&= X \left( X^T X + \lambda I \right) \left( X^T X + \lambda I \right)^{-1}
\\&= X
,\end{align}
and so left-multiplying the first and last lines by $\left( X X^T + \lambda I \right)^{-1}$ yields (**).
Plugging the transpose of (**) into (*), we get
$$
y_\text{test} = y^T (K + \lambda I)^{-1} \underbrace{X^T x_\text{test}}_{K_\text{test}}
,$$
where $K_\text{test}$ is the $n \times 1$ vector of kernel evaluations from the training points to the test point. Now, the training step is basically just to precompute the vector $y^T (K + \lambda I)^{-1}$ (via e.g. a Cholesky solve), and so at test time you just need to compute the vector of $n$ kernel values and take a single dot product.
