Orthogonality in the proof of the representer theorem

Question

I'm following these lecture notes on the representer theorem in the context of an SVM.

In terms of the notation there, let $f^*$ be the element in the reproducing kernel Hilbert space that is a solution to the regularized optimization problem given data $(x_i, y_i)$, $i=1\ldots n$.

The notes proceed as follows for a given $f$ (not necessarily the solution)

Assume $f = f_s + f_\bot$ where $f_s$ lives in the subspace spanned by the data vectors, so that $f_s = \sum_{i=1}^n a_i k(x_i , .)$ and (as far as I can tell) $f_\bot = f-f_s$, i.e. it is just everything else.

Then, in terms of evaluating the terms that arise in the loss function we have:

$$ f(x_j) = \langle f, k(x_j,.) \rangle = \langle f_s , k(x_j, .) \rangle + \langle f_\bot , k(x_j, .) \rangle $$

I get that the first term works out to $f_s(x_j) = \sum_{i=1}^n a_i k(x_i, x_j)$, but it is not clear to me that the second term $f_\bot(x_j)$ is necessarily $0$. What makes that the case?

If you say it is "by construction in the definition of $f = f_s + f_\bot$", then my question is, given a decomposition $f = f_s + f_\bot$ such that $f_\bot(x_i)=0$ for all of the data vectors, how do I know that $f_s = f-f_\bot$ can be expressed as a linear combination of the just kernels for the data vectors?

Answer 1

Let's call the span of the kernels $S$. You want to think of $f_{\bot}$ being the component of $f$ orthogonal to S. If $f$ is (orthogonally) projected onto S, obtaining $f_S$, then $f_{\bot}$ is the part of $f$ "missing" from $f_S$.

Think of a vector $v = (x,y,z)$ in $\mathbb{R}^3$ being projected onto the $xy$-plane. We'd have the projected $v_{xy} = (x, y, 0)$ and the orthogonal component $v_{\bot} = (0, 0, z)$. Obviously $v = v_{xy} + v_{\bot}$. It's also clear that $v_{\bot}$ is orthogonal to any vector on the $xy$-plane, and thus their inner product would be 0. This is not fully rigorous but I hope it can give some intuition.

To answer your question more directly, $\langle f_{\bot}, k(x_j, \cdot) \rangle = 0$ because $f_{\bot}$ is defined to be exactly the function that is orthogonal to S. You know that $f_s$ can be expressed as a linear combination of kernels because $f_s$ is defined to be in the span of the kernels.

Furthermore, if you want to know why we can write $f = f_s + f_{\bot}$ in the first place, it is because every vector space can be written as a direct sum of a subspace and its orthogonal complement. If $U$ is a subspace of $V$, then $V = U \oplus U^{\bot}$, which means that any vector $v \in V$ can be written as $v = u + u^{\bot}$ for $u \in U, u^{\bot} \in U^{\bot}$. For a proof you can check most intermediate linear algebra books. Axler's Linear Algebra Done Right section 6.C covers this.

---

Edit:

I just want to reformulate my thoughts on this in a more coherent manner.

Consider a function $f \in \mathscr{F}$ where $\mathscr{F}$ is a reproducing kernel Hilbert space. Let $S = span\{k(x_i, \cdot) : i = 1, \ldots, n\}$ be a subspace of $\mathscr{F}$. We know that $\mathscr{F}$ can be written as a direct sum of a subspace and its orthogonal complement, so $\mathscr{F} = S \oplus S^{\bot}$. Therefore, every $f \in \mathscr{F}$ can be written uniquely as $f = f_s + f_{\bot}$, where $f_s \in S$ and $f_{\bot} \in S^{\bot}$. To be clear, $S^{\bot} = \{f \in \mathscr{F} : \langle s, f \rangle = 0 \forall s \in S\}$, i.e. $S^{\bot}$ contains all functions in $\mathscr{F}$ that are orthogonal to every function in $S$.

Now we can see that $\langle f_{\bot}, k(x_i, \cdot) \rangle = 0$ for all $i$ since $k(x_i, \cdot) \in S$ and $f_{\bot} \in S^{\bot}$. Additionally, since $f_s \in S$ we know $f_s$ lies in the span of the kernels and thus can be written as a linear combination of them $f_s = \sum \alpha_ik(x_i, \cdot)$.

Answer 2

given a decomposition $f = f_s + f_\bot$ such that $f_\bot(x_i)=0$ for all of the data vectors, how do I know that $f_s = f-f_\bot$ can be expressed as a linear combination of the just kernels for the data vectors?

We have the function values at the sample points $f_i = f(x_i)$, and have to construct $f_s(x) = \sum_{j=1}^{n} a_j k(x, x_j)$ by picking the $a_i$. If we select the $a_i$ by requiring that $f(x_i) = f_s(x_i)$ (on the test points) we end up with a (square) linear system of equations:

$$ f_i = K_{ij} a_j \\ i,j \in {1 \ldots n} $$ where $f_i = f(x_i)$, $K_{ij} = k(x_i, x_j)$; and this has a unique solution for the $a_j$ given that $k$ is positive definite (i.e. $K$ is invertable). Thus the unique solution where $f_s(x_i) = \sum_j a_j k(x_i, x_j) = f(x_i)$ exists.

[N.b. this is my current understanding, if anyone has a reference that makes this construction explicit, I'd appreciate being pointed to it since I feel like I'm reading a lot into the lecture notes.]