# Least squares kernel trick

I was reading this about least squares and came cross the following claim.

$\displaystyle\min_w : |X^Tw - y|_2^2 + \lambda |w|_2^2$ solution of this least squares is in $\operatorname{span}(X)$, I am trying to understand the proof for this.

I found following article which states that any vector can be expressed as sum of orthogonal vectors and so we can choose $Xv$ which is in the $\operatorname{span}(X)$ and $r$ orthogonal vector to range of $x$ to represent $w$.

https://people.eecs.berkeley.edu/~russell/classes/cs194/f11/lectures/CS194%20Fall%202011%20Lecture%2007.pdf

But I don't understand how this proves optimal $w$ being in $\operatorname{span}(X)$.

Can you anyone help me in proving this.

• write $w = v+u$ where $v \in span(X), u \not \in span(X)$, so that $X^T w = X^T(v+u) = X^T v$, and hence it is always better to choose $u = 0$ since it will reduce $\|v+u\|^2$ without changing $\|X^T (v+u)-y\|^2$ – reuns Oct 7 '16 at 0:14
• I forgot to mention that $v,u$ lie in two different subspace, so that $\|v+u\|^2 = \|v\|^2+\|u\|^2$ – reuns Oct 7 '16 at 0:18
• By $\operatorname{span}(X)$, do you mean the span of the set of columns of $X$? $\qquad$ – Michael Hardy Oct 7 '16 at 0:45
• @MichaelHardy if $X$ is not square, it has to be the columns, and if it is the rows, then it is not true anymore that the optimum is in $span(X)$. @ Kumaran here it is what I meant : $v \in span(X)$, $u \in span(X)^\perp$ so that $X^T u = 0$ – reuns Oct 7 '16 at 0:48
• @user1952009, Thanks. That proves it. – Kumaran Oct 7 '16 at 5:58

Write $w = v + u$ where $v \in \operatorname{span} \left( x \right)$, $u \notin \operatorname{span} \left( x \right)$, namely $\left\| v + u \right\|^{2} = \left\| v \right\|^{2} + \left\| u \right\|^{2}$.
Hence ${X}^{T} w = {X}^{T} \left( v + u \right) = {X}^{T} c$. This suggests it is always best to choose $u = 0$ since it reduces $\left\| v + u \right\|^{2}$ without changing $\left\| {X}^{T} \left( u + v \right) - y \right\|^{2}$.