6
$\begingroup$

$w = (X^TX)^{-1}X^Ty$

Equation above produces weight $w$ which solves quadratic minimization problem in linear functions.

From my understanding, the goal is to find $w$ such that:

$Xw ≈ y$

Thus, I need to minimize this function:

$||Xw-y||^2$

According to wikipedia, Euclidean norm is used to minimize this function:

$2X^T(Xw - y) = 0$

Then this equation is differentiated with respect of $w$, from my understanding we use multivariable chain rule:

$X^TXw-X^Ty=0$

$X^TXw=X^Ty$

$w=(X^TX)^{-1}(X^Ty)$

Somehow, by utilizing Euclidean norm, I minimized the function, but I'm unable to understand how does it exactly work.

Why is Euclidean norm used to solve quadratic minimization problems in linear functions?

$\endgroup$
3
  • $\begingroup$ From here $2X^T(Xw - y) = 0$ we simply cancel out the factor $2$ and obtain the result. $\endgroup$
    – user
    Commented Mar 28, 2018 at 9:44
  • $\begingroup$ @gimusi For some reason I couldn't understand that part which seems to be very simple. Why is 2 cancelled out? $\endgroup$
    – ShellRox
    Commented Mar 28, 2018 at 13:08
  • 1
    $\begingroup$ It is as for $2xy=0 \implies xy=0$, just a trivial cancellation $\endgroup$
    – user
    Commented Mar 28, 2018 at 13:10

3 Answers 3

6
$\begingroup$

The best way to explain, in my opinion, is by projection.

Since $Xw = y$ has not an exact solution we look for $Xw = \bar y$ where $\bar y$ is the projection of $y$ in $Col(X)$.

The error is $e=y-\bar y=y-Xw$ and it is miminized when $e$ is orthogonal to $Col(X)$ that is

$$X^Te=X^T(y-Xw)=0\implies X^Ty=X^TXw\implies w=(X^TX)^{-1}X^Ty$$

$\endgroup$
4
  • 1
    $\begingroup$ And here Strang explains this in a lecture: youtu.be/Y_Ac6KiQ1t0?t=18m47s $\endgroup$ Commented Mar 28, 2018 at 13:46
  • $\begingroup$ Thank you for your answer and the link about projection. I'm going to read link you provided to understand orthogonal projections so I can understand the answer. $\endgroup$
    – ShellRox
    Commented Mar 28, 2018 at 14:22
  • $\begingroup$ @ShellRox You are welcome! Bye $\endgroup$
    – user
    Commented Mar 28, 2018 at 14:30
  • $\begingroup$ Thank you, From my understanding It is simply equated to zero since dot product is zero on orthogonal vectors. $\endgroup$
    – ShellRox
    Commented Mar 31, 2018 at 14:58
2
$\begingroup$

I'm not sure if this is what you are after, but perhaps worth pointing out:

You can ask the same question for any norm you like, not just the Euclidean one. The calculations are most convenient when the norm comes from an inner product. What you are minimizing is $\|Xw-y\|$, so changing the norm often changes the minimizer $w$. What changes for different norms is that the transpose is replace by the adjoint with respect to the inner product.

If the inner product on the domain is given by a positive definite matrix $P$ and the one the target side by $Q$, then the minimizer is $w=(X^TQX)^{-1}X^TQy$, which is independent of $P$, since we are only using the norm in the target space. The Euclidean case $P=I$ and $Q=I$.

$\endgroup$
2
  • $\begingroup$ Thank you for the answer. In your example, I couldn't completely understand the definition of variable $Q$, Is it matrix too? $\endgroup$
    – ShellRox
    Commented Mar 28, 2018 at 14:57
  • 1
    $\begingroup$ @ShellRox Yes, both $P$ and $Q$ are both symmetric positive definite matrices. Any inner product can be written as $(x,y)=x\cdot Qy$ for some matrix of that kind. $\endgroup$ Commented Mar 28, 2018 at 15:34
2
$\begingroup$

The Euclidean norm is the quadratic norm induced by the scalar product $$<x,y> = \sum_{k=1}^nx_k y_k \mbox{ for } x= (x_1 \ldots x_n)^T, \, y=(y_1 \ldots y_n)^T$$ $$ \Rightarrow ||x-y||^2 =<x-y,x-y> = \sum_{k=1}^n(x_k-y_k)^2$$

So, it is no surprise that quadratic optimization problems involve the concept of orthogonality.

For example, the best quadratic approximation $y_U$ within a subspace $U$ for a vector $y$ is the orthogonal projection $P_Uy$ of $y$ onto $U$, because for any $x \in U$ we have: $$ ||x - y||^2 = ||x - P_Uy + P_Uy - y||^2 \stackrel{(P_Uy - y)\perp U}{=}||x - P_Uy||^2 + ||P_Uy - y||^2 \geq ||P_Uy - y||^2$$ So, the quadratic minimum is attained for $$y_U = P_Uy$$ In your example you need only to know that $X(X^TX)^{-1}X^T = P_U$ is the orthogonal projector onto the subspace $U$ spanned by the columns of $X$ (You may find this for example here.):

$$y_U = P_Uy = X(X^TX)^{-1}X^Ty = Xw \mbox{ where } w= (X^TX)^{-1}X^Ty$$

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. I'm going to read link you provided to understand orthogonal projections so I can understand the answer. $\endgroup$
    – ShellRox
    Commented Mar 28, 2018 at 14:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .