0
$\begingroup$

Suppose we have a system of equations $Ax=b$ which has no solutions. Then, we need to find a certain $\bar{x}$ such that $A\bar{x} - b$ is minimal. Apparently this $\bar{x}$ we're looking for is a solution to the equation $A^TAx = A^Tb.$ This has something to do with projections and orthogonality but I don't understand how and why. I have tried looking online but I can't find intuitive explanations (i.e. geometric) or simple derivations as to why $\bar{x}$ must satisfy $A^TAx = A^Tb.$ (where the transpose comes from, etc.) One explanations I'm looking at states it as follows:

$Ax-b$ is the orthogonal projection of the zero vector $0$ on the set of vectors of the form $Ax-b, x \in \mathbb{R^n}$. It is characterized by the condition that $A\bar{x} -b$ is orthogonal to all vectors $Av, v \in \mathbb{R^n}$.

But I really don't understand what is meant by this. Can anyone clear this passage (or the equation itself) up for me?

$\endgroup$

2 Answers 2

2
$\begingroup$

You want to find the $x$ that minimizes the distance between $Ax$ and $b$, that is, you want to find x such that

$$ f(x) = || Ax - b|| = (Ax - b)^T(Ax -b) $$

is minimum. A possible solution to this problem is to find $x$ such that $\nabla f(x) = 0$:

$$ \nabla f(x) = 2(A^TA x - A^T b) $$

The solution to the problem is then reduced to solving

$$ A^TA x = A^Tb $$

$\endgroup$
2
  • $\begingroup$ Can you help me understand the text in the yellow box? It's kind of puzzling me. $\endgroup$ Nov 8, 2016 at 20:47
  • $\begingroup$ Call $u=Ax-b$. Then your statement says: $u$ is the projection of $0$ onto $u$, is that correct? because I cannot make sense out of it $\endgroup$
    – caverac
    Nov 8, 2016 at 20:56
0
$\begingroup$

Consider the projection $b'$ of $b$ on the range of $A$ (call it $R$). Splitting $b$ in $b'$ and $b_p$ gives $b = b' + b_p$, where $b_p$ is orthogonal to $R$ and is a measure for the error. This error is as small as possible if the length of $b_p$ is as small as possible and that is the case if $b_p$ is perpendicular to $R$.

Because $b'$ lies in $R$, $Ax = b'$ is solvable.

We have to solve $Ax = b'= b - b_p$. Since $b_p$ is orthogonal to $R$, the inner product of the column vectors of $A$ and $b_p$ equals zero (i.e. $b_p$ is in the null space of $A^T$). In matrix notation $A^T b_p = 0$.

Multiplying both sides of $Ax = b'= b - b_p$ with $A^T$: $A^T Ax = A^T (b - b_p) = A^T b - A^T b_p = A^T b$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.