Solving $Ax = b$ with $A^TAx = A^T b$

Question

Let $A \in \mathbb R^{m\times n}$ and $b \in \mathbb R^{n}$ where $m < n$. Can the linear system of equations $Ax=b$ be solved with $A^TAx = A^T b$?

How and why is it possible?

Answer 1

TL;DR: you can but you really shouldn't.

Suppose that $Ax = b$ has a solution. Then indeed $A^\top Ax = A^\top b$. Conversely, if $A^\top A x = A^\top b$. Then $Ax-b$ is in the nullspace of $A^\top$ so it must be perpendicular to the column space of $A$. But since $Ax = b$ has a solution, $b$ is in the column space of $A$ and thus $Ax - b$ is. Since $Ax -b$ is both in the column space of $A$ and perpendicular to it, it must be zero. Thus $Ax = b$. To conclude, provided $Ax = b$ has a solution, then $x$ is such a solution if, and only if, it satisfies $A^\top Ax = A^\top b$.

So if $Ax = b$ possesses a solution, then one way of computing this solution, at least if one ignores rounding errors, is to compute the Moore-Penrose pseudoinverse $(A^\top A)^\dagger$ of $A^\top A$ and then compute $x = (A^\top A)^\dagger A^\top b$. One can then check whether $Ax = b$. If this check fails, then $Ax = b$ has no solutions. If this check succeeds, then all solutions to this equation are given by $x + y$ for $y$ in the nullspace of $A$.

All of this said, this is a terrible way of solving $Ax = b$ in practice. When $A$ has more rows than columns, the matrix $A^\top A$ is guaranteed to be singular so solving the system $A^\top Ax = A^\top b$ is plagued by all sorts of numerical stability issues. There are much better ways of solving this problem. If $A$ has full row-rank, then the minimum norm solution is given by the normal equations $x = A^\top (AA^\top)^{-1}b$, which can be computed by solving a square, nonsingular system. (A more accurate way of solving the normal equations uses $LQ$ factorization.) The full solution set can be computed using any number of factorizations (pivoted $LU$, $QR$, $LQ$, SVD) of the matrix $A$ directly without any need to compute with the singular matrix $A^\top A$.