[Linear Algebra] Normal Equation

Normal Equation

• Given a least square problem $A \textbf{x} \simeq \textbf{b}$, we obtain

  • $A^T (\textbf{b} - A \hat{\textbf{x}}) = \textbf{0}$
  • $A^T A \hat{\textbf{x}} = A^T \textbf{b}$, which is called the normal equation

• This can be viewed as a new linear system $C \hat{\textbf{x}} = \textbf{d}$, where a square matrix $C = A^T A \in \mathbb{R}^{n \times n}$, and $\textbf{d} = A^T \textbf{b} \in \mathbb{R}^n$

  • if $C = A^T A$ is invertible, then the solution is computed as $\hat{\textbf{x}} = \begin{pmatrix} A^T A \end{pmatrix}^{-1} A^T \textbf{b}$