# representer theorem in kernel ridge regression for slightly modified loss function

It is very well known that for a problem of the form

$$\min_f\frac{1}{n}\sum_{i=1}^n (y_i -f(x_i))^2 + \lambda \|f\|^2_\mathcal{H}, \quad\lambda\ge0$$

for a $$f$$ in a RKHS $$\mathcal{H}$$ has a solution

$$f(x) = \sum_{i=1}^nc_iK(x_i,x)\tag{1}$$

where $$c$$ solves the system of equations

$$(K+\lambda n \textbf{1})c = y\tag{2}$$

for the kernel $$K$$ of the RKHS $$\mathcal{H}$$. My question is can this be generalized to cases where we look at

$$\min_f\frac{1}{n}\sum_{i=1}^n \big(y_i - \beta_i^T\big[f(x_1);\cdots;f(x_m)\big]\big)^2 + \lambda \|f\|^2_\mathcal{H}$$

for given vectors $$\beta_i$$ and $$\lambda >0$$. I've found a general version of the representer theorem which covers this kind of form, too. I.e. the solution is still of the form $$(1)$$. However, is there also a generalization of $$(2)$$ in this case? A proof / reference would be much appreciated!

• Have you made a typo? Do you actually want the dimension of the domain of $f$ to be the same as the number of data points, and $x_i$ to be evaluated as the $i$'th coordinate? If so, this is very strange, since this would be a trivial problem.
– Hans
Commented Dec 5, 2021 at 15:29
• @Hans I've edited my question. What I mean is, that compared to $(1)$ where $f$ for the pair $(x_i,y_i)$ only takes into account a single feature $x_i$, in $(2)$ I want to build a vector for all the vaules of features $x_i$
– math
Commented Dec 5, 2021 at 17:30
• @math I think Hans is asking if you mean $x_i$ to have $p$ features, in which case you want $f$ to be a function retuning a $p$ vector, $\beta$ to be a $p$ vector, and you can write $$\min_f\frac1n\sum_{i=1}^n(y_i - \beta_i^Tf(x_i))^2 + \lambda ||f||^2_{\mathcal{H}}\,.$$ Is this what you're interested in?
– Nate
Commented Dec 7, 2021 at 1:40
• @Nate thanks for your comment. What I mean is, that $f$ is a scalar valued function. It takes a single argument from the feature space $X$. However in the loss function I use for each term $y_i - \beta_i^T[f(x_1),\dots,f(x_m)]$ always the set of ALL observed values of the features: $x_1,\dots,x_m$ and stack it into a vector. I hope this makes it clear
– math
Commented Dec 7, 2021 at 16:50
• @Hans I slightly updated the question. Note that $[f(x_1),\dots,f(x_m)]$ does not depend on $i$. It is the vector of stacked values of $f$ evaluated at all given realizations of features $x_1,\dots,x_m$.
– math
Commented Dec 7, 2021 at 16:51

Suppose the domain of the functions of $$\mathcal H$$ is $$X$$. Let $$k: X\times X\rightarrow \mathbf R$$ be the reproducing kernel, which is symmetric and positive semidefinite. Define $$L[f] := \sum_{i=1}^n \big(y_i -\beta_i^ T\vec f\big)^2 + \lambda \|f\|^2_\mathcal{H}, \quad\lambda\ge0$$ where $$\vec f := \big[f(x_1),f(x_2),\cdots,f(x_m)\big]^T$$ and $$\beta_i$$ is a column matrix. Let $$M:= \{1,2,\cdots,m\}$$ and $$N:= \{1,2,\cdots,n\}$$. (The factor $$\frac1n$$ in the original question formulation is absorbed into $$\lambda$$ so as to abbreviate the notations.)

$$\forall f\in\mathcal H,$$ $$f=\sum_{i=1}^m c_i k(\cdot,x_i)+v$$ for some $$(c_i)_{i\in M}$$ and some $$(v\in\mathcal H) \perp \operatorname{span}(\{K(\cdot,x_i)|i\in M\})$$ or $$\langle v,k(\cdot,x_i)\rangle=0,\,\forall i\in M$$. So for $$\forall j\in M$$ \begin{align} f(x_j)&=\langle f,k(\cdot,x_j) \rangle \\ &=\sum_{i=1}^m c_i \langle k(\cdot,x_i),k(\cdot,x_j)\rangle +\langle v,k(\cdot,x_j)\rangle \\ &= \sum_{i=1}^m c_i k(x_i,x_j), \end{align} and $$f(x_j)$$ is independent of $$v$$.
\begin{align} \|f\|^2_{\mathcal H}&=\Big\langle \sum_{i=1}^m c_i k(\cdot,x_i), \sum_{j=1}^m c_i k(\cdot,x_j) \Big\rangle+\|v\|_\mathcal H^2 \\ &= \sum_{i,j=1}^m c_i k(x_i,x_j) c_j+\|v\|^2_\mathcal H \end{align} since $$v\perp$$ span$$(k(\cdot,x_i)|i\in M)$$.

Therefore the $$f$$ that minimizes $$L[f]$$ should have $$v=0$$. We denote such $$f$$ by $$f^*$$, and $$f^*:=\operatorname{arg min}_{f \in\mathcal H}L[f]=\sum_{i=1}^m c_i k(\cdot,x_i)$$ and $$f^*(x_j)=\sum_{i=1}^m c_i k(x_j,x_i),\quad\forall i\in M,$$ or in the matrix form $$\vec {f^*}=Kc$$ where $$m\times m$$ matrix $$K$$ has $$(j,i)$$'th entry $$K_{j,i}:=k(x_j,x_i),\,\forall i,j \in M$$ and $$m\times 1$$ matrix $$c$$ has entry $$c_i,\,\forall i\in M$$. Matrix $$K$$ is symmetric since the function $$k(\cdot,\cdot)$$ is symmetric.

Let the $$n\times 1$$ matrix $$y:=[y_i]_{i\in N}$$, and $$n\times m$$ matrix $$\beta:= [\beta_i^T]_{i\in N}$$ be the matrices constructed from stacking the components on the right hand side vertically. Substituting $$f=f^*$$ into $$L[f]$$, we have \begin{align} L[f^*]&=(y-\beta Kc)^T(y-\beta Kc)+\lambda c^T Kc \\ &= c^T(K\beta^T\beta K+\lambda K)c-2y^T\beta K c +y^Ty. \end{align} Thus $$L[f^*]$$ minimizes at $$0=\big(K\beta^T\beta K+\lambda K\big)c-K \beta^T y=Ku,$$ with $$u:=(\beta^T\beta K+\lambda I)c-\beta^T y.$$ It is true iff $$u$$ is in the null space of $$K$$ or that $$u$$ is a zero eigenvector $$K$$. If matrix $$K$$ is positive definite, the left $$K$$'s on both sides of the equation cancels and we have $$c= (\beta^T\beta K+\lambda I)^{-1}(\beta^Ty+u)$$ so long as $$\lambda>0$$ or $$\beta$$ is of full rank. If $$K$$ is positive definite, $$u=0$$.

Remark:

The kernel function $$k(⋅,⋅)$$ is positive definite. That however does not guarantee the positive definiteness of matrix $$K$$. For example, the $$K$$ resulting from $$\vec x$$ with duplicating $$x_i$$ is not positive definite. All distinct $$x_i$$'s would not guarantee that either.

$$\{k(\cdot,x_i)\}_{i\in M}$$ with $$x_i$$'s all distinct is not necessarily linearly independent. For example, the linear kernel $$k(x,y)=x^Ty,\, \forall x,y\in R^p$$ for some natural number $$p$$. $$\{k(\cdot,x_i)\}_{i\in M}$$ is linearly dependent when $$\{x_i\}_{i\in M}$$ is.

• Thanks Hans, it is clear now. Just one last question. Usually the kernel matrix is just positive semi-definite, or am I missing something?
– math
Commented Dec 8, 2021 at 18:52
• Sure we can delete the first two comments
– math
Commented Dec 18, 2021 at 18:52
• I have one more question which troubles me. I've implemented the solution....but I get different results when I use $c_1= (\beta^T\beta K+\lambda I)^{-1}(\beta^Ty)$ and $c_2=(K\beta^T\beta K + \lambda K)^{-1}K\beta^Ty$. Tha means $c_1\neq c_2$ Why is that the case? I've checked the implementation very carefully, i.e. I doubt there is an error. I have a benchmark solution which is the result I get from $c_1$.
– math
Commented Dec 18, 2021 at 18:55
• @math: I have stated in the original answer that $K$ needs to be positive-definite. Have you checked that (or the nonsingularity)? In numerical computation, you need to compute the ratio of the smallest over the largest eigenvalues of $K$. If that is very small and comparable to the computer floating number resolution, $K$ is effectively singular. I have added the general solution into the answer. But check the singularity of $K$ first before worrying about the degeneracy.
– Hans
Commented Dec 19, 2021 at 6:23
• Many thanks for your patience. So I've implemented it in python. As it seems numpy is able to do a Cholesky decomposition for K as well as it says that all eigenvalues are positive. So that $K$ should be positive definite. For the ratio of smallest to larger eigenvalues of K I get the followin $(3.6817381615078046e-16+0j)$. Do you think that is the reason that $c_1$ and $c_2$ differ as this ratio is virtually zero? I'm still puzzeled that numpy doens't throw an error for inverting $K$, although it takes very long. Again thanks for your patience!
– math
Commented Dec 19, 2021 at 17:23