Skip to main content

Subsection 4.2.2 The Method of Normal Equations

Consider again the LLS problem: Given \(A \in \Cmxn \) and \(b \in \Cm \) find \(\widehat x \in \Cn \) such that

\begin{equation*} \| b - A \widehat x \|_2 = \min_{x \in \Cn} \| b - A x \|_2 . \end{equation*}

We list a sequence of observations that you should have been exposed to in previous study of linear algebra:

  • \(\widehat b = A \widehat x \) is in the column space of \(A \text{.}\)

  • \(\widehat b \) equals the member of the column space of \(A\) that is closest to \(b \text{,}\) making it the orthogonal projection of \(b \) onto the column space of \(A \text{.}\)

  • Hence the residual, \(b - \widehat b \text{,}\) is orthogonal to the column space of \(A \text{.}\)

  • From Figure 4.2.1.2 we deduce that \(b - \widehat b = b - A \widehat x \) is in \(\Null( A^H ) \text{,}\) the left null space of \(A \text{.}\)

  • Hence \(A^H ( b - A \widehat x ) = 0 \) or, equivalently,

    \begin{equation*} A^H A \widehat x = A^H b. \end{equation*}

    This linear system of equations is known as the normal equations.

  • If \(A \) has linearly independent columns, then \(\rank( A ) = n \text{,}\) \(\Null( A ) = \emptyset \text{,}\) and \(A^H A \) is nonsingular. In this case,

    \begin{equation*} \widehat x = ( A^H A )^{-1} A^H b. \end{equation*}

    Obviously, this solution is in the row space, since \(\Rowspace( A ) = \Cn \text{.}\)

With this, we have discovered what is known as the Method of Normal Equations. These steps are summarized in Figure 4.2.2.1

images/Chapter04/FundamentalSpacesLLSLinIndep.pptx
Figure 4.2.2.1. Solving LLS via the Method of Normal Equations when \(A \) has linearly independent columns (and hence the row space of \(A \) equals \(\Cn \)).
Definition 4.2.2.2. (Left) pseudo inverse.

Let \(A \in \Cmxn \) have linearly independent columns. Then

\begin{equation*} A^\dagger = ( A^H A )^{-1} A^H \end{equation*}

is its (left) pseudo inverse.

Homework 4.2.2.1.

Let \(A \in \Cmxm \) be nonsingular. Then \(A^{-1} =A^\dagger \text{.}\)

Solution
\begin{equation*} A A^\dagger = A ( A^H A )^{-1} A^H = A A^{-1} A^{-H} A^H = I I = I. \end{equation*}
Homework 4.2.2.2.

Let \(A \in \Cmxn \) have linearly independent columns. ALWAYS/SOMETIMES/NEVER: \(A A^\dagger = I \text{.}\)

Hint

Consider \(A = \left( \begin{array}{c} e_0 \end{array} \right) \text{.}\)

Answer

SOMETIMES

Solution

An example where \(A A^\dagger = I \) is the case where \(m = n \) and hence \(A \) is nonsingular.

An example where \(A A^\dagger \neq I\) is \(A = e_0 \) for \(m \gt 1 \text{.}\) Then

\begin{equation*} \begin{array}{l} A A^\dagger \\ ~~~=~~~~ \lt \mbox{ instantiate } \gt \\ \left( \begin{array}{c} 1 \\ 0 \\ \vdots \end{array} \right) \begin{array}[t]{c} \underbrace{ \left( \begin{array}[t]{c} \underbrace{ \left( \begin{array}{c} 1 \\ 0 \\ \vdots \end{array} \right)^H \left( \begin{array}{c} 1 \\ 0 \\ \vdots \end{array} \right) } \\ 1 \end{array} \right)^{-1} } \\ 1 \end{array} \left( \begin{array}{c} 1 \\ 0 \\ \vdots \end{array} \right)^H \\ ~~~=~~~~ \lt \mbox{ simplify } \gt \\ \left( \begin{array}{c} 1 \\ 0 \\ \vdots \end{array} \right) \left( \begin{array}{c c c} 1 \amp 0 \amp \cdots \end{array} \right)\\ ~~~=~~~~ \lt \mbox{ multiply out } \gt \\ \left( \begin{array}{c c c} 1 \amp 0 \amp \cdots \\ 0 \amp 0 \amp \cdots \\ \vdots \amp \vdots \amp \end{array} \right) \\ ~~~=~~~~ \lt m \gt 1 \gt \\ \neq I. \end{array} \end{equation*}
Ponder This 4.2.2.3.

The last exercise suggests there is also a right pseudo inverse. How would you define it?

login