How to Prove the Semi-parametric Representer Theorem This question concerns the generalized Representer Theorem, due to Schölkopf, Herbrich, and Smola. In this magnificent work, the authors provide two versions of the Representer Theorem, a non-parametric, and a semi-parametric one. Though, they provide a proof only for the non-parametric version, while they say that the proof for the semi-parametric version is slightly more technical, but straightforward.
I fully understand the proof for the non-parametric version, but unfortunately I cannot find a way in order to start the proof of the semi-parametric.
Below, I give the statements of the above two versions of the Representer Theorem, as well as the proof for the non-parametric case, and I would like to discuss about the proof of the semi-parametric version.
#Theorem 1 (Non-parametric Representer Theorem)
Suppose we are given a nonempty set $\mathcal{X}$, a positive definite real-valued kernel $k$ on $\mathcal{X}\times\mathcal{X}$, samples $(\mathbf{x}_1,y_1),\cdots,(\mathbf{x}_m,y_m)\in\mathcal{x}\times\mathbb{R}$, a strictly monotonically increasing real-valued function $g$ on $[0,\infty)$, an arbitrary cost function $c\colon(\mathcal{x}\times\mathbb{R}^2)^m\to\mathbb{R}\cup\{\infty\}$, and a class of functions
$$
\mathcal{F}=\bigg\{
f\in\mathbb{R}^{\mathcal{X}} \mid f(\cdot)=\sum_{i=1}^{\infty}\beta_i k(\cdot, \mathbf{z}_i), \beta_i\in\mathbb{R}, \mathbf{z}_i\in\mathcal{X}, \lVert f \rVert < \infty
\bigg\}.
$$
Here, $\lVert\cdot\rVert$ denotes the norm in the Reproducing Kernel Hilbert Space (RKHS) $\mathcal{H}$ associated with $k$. Then any $f\in\mathcal{F}$ minimizing the regularized risk functional
$$
c
\Big( 
(\mathbf{x}_1,y_1,f(\mathbf{x}_1)), \cdots, (\mathbf{x}_m,y_m,f(\mathbf{x}_m))
\Big)
+
g\big(\lVert f \rVert\big)
$$
admits a representation of the form
$$
f(\cdot) = \sum_{i=1}^{m} \alpha_i k(\cdot,\mathbf{x}_i).
$$
Proof: Let $\phi: \mathcal{X}\to\mathbb{R}^{\mathcal{X}}$,
$$
\mathbf{x}\mapsto k(\cdot,\mathbf{x}).
$$
Since $k$ is a reproducing kernel, evaluation of the function $\phi(\mathbf{x})$ on the point $\mathbf{x}'$ yields
$$
(\phi(\mathbf{x}))(\mathbf{x}')=k(\mathbf{x}',\mathbf{x})=\langle \phi(\mathbf{x}'), \phi(\mathbf{x}) \rangle,
$$
for all $\mathbf{x},\mathbf{x}'\in\mathcal{X}$. Here $\langle \cdot,\cdot \rangle$ denotes the dot product in $\mathcal{H}$. Given $\mathbf{x}_1,\cdots,\mathbf{x}_m$, any $f\in\mathcal{F}$ can be decomposed into a part that lives in the span of the $\phi(\mathbf{x}_i)$, and a part which is orthogonal to it, i.e.
$$
f = \sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i) + u,
$$
for some $\alpha\in\mathbb{R}^m$ and $u\in\mathcal{F}$ satisfying fot all $j$,
$$
\langle u,\phi(\mathbf{x}_j) \rangle = 0.
$$
Using the latter and the reproducing property mentioned above, application of $f$ to an arbitrary point $\mathbf{x}_j$ yields
$$
f(\mathbf{x}_j) = 
\Big\langle
\sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i) + u,
\phi(\mathbf{x}_j)
\Big\rangle
=
\sum_{i=1}^{m} \alpha_i 
\Big\langle 
\phi(\mathbf{x}_i),\phi(\mathbf{x}_j)
\Big\rangle,
$$
which is independent of $u$. Consequently, the first term of the regularized risk functional is independent of $u$. As for the second term, since $u$ is orthogonal to $\sum_{i=1}^{m}\alpha_i\phi(\mathbf{x}_i)$, and $g$ is strictly monotonic, we get
$$
g\big(\lVert f \rVert\big)
= 
g\bigg(\bigg\lVert 
\sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i) + u
\bigg\rVert\bigg)
=
g\bigg(
\sqrt{
\bigg\lVert 
\sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i)
\bigg\rVert^2
+
\bigg\lVert 
u
\bigg\rVert^2
}
\bigg)
\geq
g\bigg(
\bigg\lVert 
\sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i)
\bigg\rVert
\bigg),
$$
with equality iff $u=0$. Setting $u=0$ thus, does not affect the first term of the regularized risk functional, while strictly reducing the second term - hence, any minimizer must have $u=0$. Consequently, any solution takes the form $f=\sum_{i=1}^{m}\alpha_i\phi(\mathbf{x}_i)$, i.e., using the reproducing property,
$$
f(\cdot) = \sum_{i=1}^{m}\alpha_i k(\cdot,\mathbf{x}_i).
$$
Q.E.D.
Now, the statement of the semi-parametric version extends the non-parametric as follows:
#Theorem 2 (Semi-parametric Representer Theorem)
Suppose that, in addition to the assumptions of the previous theorem, we are given a set of $M$ real-valued functions $\{\psi_p\}_{p=1}^{M}$ defined on $\mathcal{X}$, with the property that the $m\times M$ matrix $\big( \psi_p(\mathbf{x}_i) \big)_{ip}$ has rank $M$. Then, any $\tilde{f}:=f+h$, with $f\in\mathcal{F}$ and $h\in\operatorname{span}\{\psi_p\}$, minimizing the regularized risk functional
$$
c
\Big( 
(\mathbf{x}_1,y_1,\tilde{f}(\mathbf{x}_1)), \cdots, (\mathbf{x}_m,y_m,\tilde{f}(\mathbf{x}_m))
\Big)
+
g\big(\lVert f \rVert\big),
$$
admits a representation of the form
$$
\tilde{f}(\cdot)
=
\sum_{i=1}^{m}\alpha_i k(\cdot,\mathbf{x}_i)
+
\sum_{p=1}^{M}\beta_p \psi_p(\cdot),
$$
with unique coefficients $\beta_p\in\mathbb{R}$, for all $p=1,\cdots,M$.
It would be nice if you could provide a meaningful sketch of the proof. I think it may help some other people as well, who study this theory, but unfortunately do not have the appropriate background to prove such theorems by themselves (yet!). Thanks a lot!
 A: Suppose that we have $\tilde f = f + h$ as described. Let $V = span( k(\cdot, x_i) )_{i=1,...,m}$. We can write any function $f \in \mathcal{F}$ as $f = f_s + f_p$ where $f_s \in V$ and $f_p \in V^{\perp}$.
This means that $$\tilde f(x_i) = f(x_i) + h(x_i) = f_s(x_i) + f_p(x_i) + h(x_i)$$ but since $f_p \in V^{\perp}$ we have that $f_p(x_i) =0$. Which yields: $$\tilde f(x_i) = f(x_i) + h(x_i) = f_s(x_i) + h(x_i)$$
Thus $$c( (x_i, y_i, \tilde f(x_i))_{i=1,...,m}) = c( (x_i, y_i, f_s(x_i) + h(x_i))_{i=1,...,m})$$ which means that $f_p$ has no effect on $c(\cdot)$. Moreover, since $$\|f\|^2 = \|f_s\|^2 + \|f_p\|^2$$ by the pythagorean theorem, we have $$\|f_s\| \le \|f\|$$ for all $f \in \mathcal{F}$. Thus $g(\|f_s\|) \le g(\|f\|)$ since $g$ is strictly increasing.
Thus we see if a function $\tilde f = f+h$ minimizes the cost function $f_p$ must be zero. Thus $\tilde f = f_s + h$ and since $f_s \in V$ we have that $$\tilde f = \sum_{i=1}^m a_i k(\cdot, x_i) + h$$
Finally when we evaluate $\tilde f(x_j) = \sum_{i=1}^m a_i k(x_j, x_i) + h(x_j)$ we get $m$ equations for $$h(x_j) = \sum_{p=1}^M \beta_p \psi_p(x_j) = \tilde f(x_j) - \sum_{i=1}^m a_i k(x_j, x_i).$$ By the assumptions on $\psi_p(x_j)$ we see that $(\psi_p(x_1),...,\psi_p(x_m))^T$ (for $p=1,2,...,M$) are linearly independent vectors, and thus the coefficients $\beta_p$ are uniquely determined.
