0
$\begingroup$

I understand why $\vec{{P}}$ (the orthogonal projection of $\vec{{b}}$ on w)
is the closest vector to $\vec{{b}}$ (The vector that does not give us a solution to the
equation and that's why we need to do the process)

But I do not understand the equation:
$$A^TA\vec{{x}}=A^T \vec{{b}}$$ Why does multiplying each side of the original equation $A\vec{{x}}=\vec{{b}}$ (We know she has no answer) by $A^T$ give us the closest answer?
Thank you

$\endgroup$
1
$\begingroup$

Given vector $\vec b$ and matrix $A$, the goal is to find $\vec x$ so that $A\vec x$ is as close to $\vec b$ as possible.

Let $W$ be the subspace of all vectors of the form $A\vec x$. Observe that $W$ is the set of all linear combinations of columns of $A$.

We are looking for the vector in $W$ that is closest to $\vec b$. Write $A\hat x$ for this vector. By the projection theorem, $A\hat x$ is the orthogonal projection of $\vec b$ onto $W$. Equivalently, $A\hat x-\vec b$ is orthogonal to every vector in $W$. As a special case, we conclude:

$$ \text{$A\hat x-\vec b$ is orthogonal to every column of matrix $A$}. \tag{*}$$

Constraint (*) can be written in matrix form as: $$ A^T(A\hat x-b) = 0,$$ which leads to the equation $A^TA\hat x=A^T\vec b$.

$\endgroup$
5
  • $\begingroup$ Thank you very much for the explanation. i just do not understand how it helps us if: $$ A^T(A\hat x-b) = 0,$$ Is a multiplication of each column of A Gives us a solution because the multiplication is equal to 0? $\endgroup$ – NFLX Nov 12 '20 at 12:41
  • $\begingroup$ @NFLX You can rewrite the matrix equation $A^T(A\hat x-b)=0$ into a system of linear equations that can be solved for the best $\hat x$. In other words, the projection theorem leads to conditions that the best $\hat x$ must satisfy. These conditions lead to an equation that we can solve. $\endgroup$ – grand_chat Nov 12 '20 at 17:38
  • $\begingroup$ (Sorry it's long) I kind of explain everything to myself and just tell me if I'm right: We are looking for the vector which is closest to $\vec{{b}}$ because $\vec{{b}}$ Is not a solution to $$A\vec{{x}}=\vec{{b}}$$. We know that $\vec{{P}}$ (the Orthogonal projection is the closest solution. So we demand that $$ A^T(\vec{{P}}-\vec{{B}}) = 0,$$ Because it tells us it's 90 degrees between $\vec{{P}}$ and $\vec{{B-P}}$ and that it proves to us that $\vec{{P}}$ is the closest? $\endgroup$ – NFLX Nov 12 '20 at 19:19
  • 1
    $\begingroup$ @NFLX Yes, $\vec u^T\vec v=0$ means the vectors $\vec u$ and $\vec v$ are orthogonal. And if $\vec P$ is the vector in $W$ that is closest to $\vec b$ then the projection theorem states that the error vector $\vec b-\vec P$ is orthogonal to every vector in $W$. $\endgroup$ – grand_chat Nov 12 '20 at 19:35
  • $\begingroup$ Excellent! really really thank you! $\endgroup$ – NFLX Nov 12 '20 at 19:41
0
$\begingroup$

I'm not able to comment, but my answer to: How to formulate ordinary least squares regression in component formalism? may address your question. The reason multiplying each side by $A^T$ helps is that while $A$ may not have an inverse, $A^TA$ typically does, allowing you to solve for $\vec{x}$.

$\endgroup$
0
$\begingroup$

@nosuchthingasmagic gives a link to a question that gives a calculus-based derivation. Here's another one.

The standard notation is $\vec y = X \vec {\beta}$. Then we note that this has no exact solution, so really $X \vec {\beta} = \vec y + \vec {\epsilon}$. If $\vec \beta$ is optimal, then $X^T \vec {\epsilon}=\vec 0$. So when we multiply both sides by $X$, $\epsilon$ disappears and we're left with $X^TX \vec {\beta} = X^T\vec y$.

Why $X^T \vec {\epsilon}=\vec 0$? Well, that's saying that every row of $X^T$ is orthogonal to $\vec {\epsilon}$. And the rows of $X^T$ represent all the observations of a particular feature. So this is saying that for each feature, the observations of that feature are uncorrelated with the errors. If there were a correlation, we could adjust the corresponding $\beta_i$ to get a better fit.

$\endgroup$
0

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.