# Orthogonality in the proof of the representer theorem

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?

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)$.

• "You know that $f_s$ can be expressed as a linear combination of kernels because $f_s$ is defined in the span of kernels" -- This might be what I'm missing. How do you prove this statement? or maybe, What does "spanning" mean in this context?
– Dave
Apr 14, 2018 at 3:13
• It's true by definition. We define $f_s$ to be the projection of $f$ onto the span of the kernels. This means $f_s \in span\{k(x_i, \cdot) | i = 1, \ldots, n\}$ which implies $f_s$ can be written as $f_s = \sum_{i=1}^n \alpha_ik(x_i, \cdot)$. It's easier to reason about in the $\mathbb{R}^3$ example, $v_{xy}$ is on the xy-plane and so we can write it as a linear combination of (1, 0, 0) and (0, 1, 0), $v_{xy} = x(1, 0, 0) + y(0, 1, 0)$. Apr 14, 2018 at 3:26
• Great answer, thanks. Aug 8, 2022 at 23:47

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.]