Subsection4.2.2The 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

Definition4.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.

Homework4.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*}
Homework4.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{.}$

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