# Least squares: How does the projection theorem lead to the normal equations?

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

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

• 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? – NFLX Nov 12 '20 at 12:41
• @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. – grand_chat Nov 12 '20 at 17:38
• (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? – NFLX Nov 12 '20 at 19:19
• @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$. – grand_chat Nov 12 '20 at 19:35
• Excellent! really really thank you! – NFLX Nov 12 '20 at 19:41

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

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