[Math] Overdetermined System Ax=b

linear algebramatrices

Let's say we have the following system of equations:
\begin{equation}
A{\bf x}={\bf b} \qquad (1)
\end{equation}
where $A$ is $N \times 4$, $\mathbf{x}$ is $4 \times 1$ (unknowns) and ${\bf b}$ is $N \times 1$.

Using linear-least square method the solution of the overdetermined system is:

\begin{equation}
(A^TA) {\bf x} = A^T {\bf b} \qquad (2)
\end{equation}

\begin{equation}
{\bf x} = (A^TA)^{-1} A^T {\bf b} \qquad (3)
\end{equation}

Why do we multiply both sides of Eq.$(1)$ by $A^T$?

Best Answer

You minimize the the (squared) expression $V=\left\| Ax-b \right\|^2$. This is equal to

$V=(Ax-b)^T(Ax-b)$

Remove $T$ from the brackets. The order of $Ax$ is changing.

$V=(x^TA^T-b^T)(Ax-b)$

Multiplying out the brackets.

$V=x^TA^TAx-x^TA^Tb-b^TAx+b^Tb$

$x^TA^Tb$ and $b^TAx$ are both scalars and they are equal. One can be replaced by another.

$V=x^TA^TAx-2x^TA^Tb+b^Tb$

To optimize this expression w.r.t $x$ it has to be calculated the derivative w.r.t $x $ and set it equal to zero. The derivative of $b^Tb$ is zero, because it has no $x$.

$\frac{\partial V}{\partial x}=2A^TAx-2A^Tb=0 \quad |:2$

$A^TAx-A^Tb=0 \quad \quad$

$A^TAx=A^Tb \quad\quad |:A^TA $

On the LHS $A^TA$ is left from $x$. If we divide both sides by $(A^TA)^{}$ then $(A^TA)^{-1}$ has to be left on the RHS as well.

$\boxed{x=(A^TA)^{-1}A^Tb}$

Related Question