2
$\begingroup$

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

https://inst.eecs.berkeley.edu/~ee127a/book/login/l_ols_kernels.html

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

$\endgroup$
7
  • 1
    $\begingroup$ 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$ $\endgroup$ – reuns Oct 7 '16 at 0:14
  • $\begingroup$ I forgot to mention that $v,u$ lie in two different subspace, so that $\|v+u\|^2 = \|v\|^2+\|u\|^2$ $\endgroup$ – reuns Oct 7 '16 at 0:18
  • 1
    $\begingroup$ By $\operatorname{span}(X)$, do you mean the span of the set of columns of $X$? $\qquad$ $\endgroup$ – Michael Hardy Oct 7 '16 at 0:45
  • 1
    $\begingroup$ @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$ $\endgroup$ – reuns Oct 7 '16 at 0:48
  • 1
    $\begingroup$ @user1952009, Thanks. That proves it. $\endgroup$ – Kumaran Oct 7 '16 at 5:58
1
$\begingroup$

Answer by @reuns:

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.