4
$\begingroup$

My professor says that "the normal equations always have a solution", even when $A$ is not full rank. HOwever, this does not make sense to me. The normal equations are

$$A^\dagger=(A^TA)^{-1}A^T$$

$A^TA$ is invertible IFF $A$ is full column rank. So, it seems to me like there is only a solution to the normal equations if $A$ is full column rank?

edit: I wonder if he meant to say "we can always find the Moore Penrose Inverse even when $A$ is not full rank". that makes more sense to me but I just wantto confirm.

$\endgroup$
2
  • 3
    $\begingroup$ $A^{T}A x=A^{T}b$ can have a solution/solutions even if $A^{T}A$ is not invertible. $\endgroup$ Sep 17, 2018 at 16:35
  • $\begingroup$ I disagree with the statement of what the normal equations are in this question. The normal equations are $A^T Ax = A^T b$. The normal equations can be derived by minimizing $\frac12 \| Ax - b \|^2$ with respect to $x$. Setting the gradient equal to $0$, we obtain $A^T (Ax - b) = 0$. It seems intuitive that there should always exist a (possibly non-unique) value of $x$ that minimizes $\frac12 \|Ax - b \|^2$, even if $A$ does not have full rank. $\endgroup$
    – littleO
    Sep 17, 2018 at 16:52

3 Answers 3

6
$\begingroup$

"The normal equations always have a solution" is the same as saying "the column space of $A^T$ is contained in the column space of $A^T A$". One way to see this is to note that the reverse containment is clearly true, and then to show that the rank of $A^T A$ is the same as the rank of $A$. This is closely related to the "four fundamental subspaces theorem"; if you're not aware of this result, pick up Gilbert Strang's book.

They do not always have a unique solution, and indeed they do not when $A$ has deficient column rank.

$\endgroup$
6
  • $\begingroup$ I guess what I'm confused by is how the normal equations even make sense at all if $A^TA$ is not invertible. $\endgroup$
    – makansij
    Sep 17, 2018 at 16:43
  • 6
    $\begingroup$ @guimption The normal equations are not $x=(A^T A)^{-1} A^T b$. They are $A^T A x = A^T b$. $\endgroup$
    – Ian
    Sep 17, 2018 at 16:43
  • $\begingroup$ Ah, that's key thank you!! $\endgroup$
    – makansij
    Sep 17, 2018 at 16:43
  • 1
    $\begingroup$ @Ian Would you have an argument for why $A^T$ and $A^TA$ have the same rank? $\endgroup$
    – Blue
    Feb 22, 2021 at 17:27
  • $\begingroup$ @Blue Basically what you need to get to is that a matrix $B$ maps its row space to its column space. Thus the column space of $A^T A$ will contain the column space of $A$ if the column space of $A$ contains the row space of $A^T$...which it certainly does, because those are the same space. $\endgroup$
    – Ian
    Mar 19, 2021 at 15:32
2
$\begingroup$

Actually I think what he meant is that you can solve $A^T A A^\dagger = A^T$ for $A^\dagger$. If $A^T A$ is invertible, the solution is $(A^T A)^{-1} A^T$; otherwise you can use Moore-Penrose.

$\endgroup$
0
$\begingroup$

I reply to this question by completing the answer by Olittle above that says that "It seems intuitive that there should always exist a (possibly non-unique) value of $x$ that minimizes $\|Ax−b\|^2$". This is true because first observe that solving the normal equation of $Ax=b$ is equivalent to the minimization of $\|Ax−b\|^2$ in the Euclidean space $\mathbb{K}^m$. Now, for $A\in \mathbb{K}^{m\times n}$, let $\mathcal{R}(A)$ denote the range of $A$ which is a closed and convex subset of $\mathbb{K}^m$ because $\mathcal{R}(A)$ is a subspace of a finite-dimensional normed space (Recall that a finite-dimensional subspace of a normed space is a closed set, see Every finite-dimension subspace of $\mathcal{X}$ is closed.). Then for any $b\in\mathbb{K}^m$ the problem: minimize $\|y−b\|^2$ for $y\in \mathcal{R}(A)\subseteq\mathbb{K}^m$ has a solution (and is unique) given that it is equivalent to the problem of the minimum distance of the point $b\in\mathbb{K}^m$ to the closed convex subset $\mathcal{R}(A)$ of the Euclidean space (which is a Hilbert space) $\mathbb{K}^m$. Denote then $\bar y$ such solution. Since $\bar y\in \mathcal{R}(A)$, then $Ax=\bar y$ has solution. This is then a minimizer of $\|Ax−b\|^2$, thus it is a solution of the normal equations of $Ax=b$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .