Solving system of overdetermined linear equations with $2$-norm

Question

Given a system of overdetermined linear equations $Ax = b$, I know that it is possible to find a solution of that problem using $2$-norm, but I have a doubt: Is it wrong to think that it is equivalent to finding a solution of the system of normal equations $A^TAx = A^Tb$?

Answer 1

It's not technically equivalent numerically and you have an error

$$ A^{T}Ax =A^{T}b \tag{1} $$

is the normal equations. You can solve $Ax=b$ with the SVD

$$ Ax = b \\ U \Sigma V^{T} x = b \\ x= V\Sigma^{\dagger}U^{T}b \tag{2}$$

if you explicitly form the normal equations you'll square the condition number $ \kappa(A)$ .Where $\kappa(A)$ is given by

$$ \kappa(A) = \frac{\sigma_{max}}{\sigma_{min}}\tag{3}$$

There are technically two different numerical methods used to solve these systems of equations, so if you do care about error typically the normal equations under the $2 $ norm is not as good.

If you solve the over-determined case. $$ A^{T}Ax = A^{T}b \tag{4}$$

$$ x = (A^{T}A)^{-1}A^{T}b \tag{5}$$