4
$\begingroup$

My professor mentioned in the lecture that minimizing $\|Ax−b\|$ is equivalent to solving the linear system $$\begin{bmatrix} -I & A\\ A^T & 0 \end{bmatrix} \begin{bmatrix} r\\ x \end{bmatrix} = \begin{bmatrix} b\\ 0 \end{bmatrix}, $$ where $r = b-Ax.$
Can somebody elaborate on why this is true and what are the advantages of writing the least square problem in this way? What is the relationship between the optimization problem and the solution of the linear system?

$\endgroup$
1
  • $\begingroup$ Something is odd here. If I calculated correctly the first row evaluates to $2Ax -2b=0$, which is solvable iff $Ax-b=0$ is. But the whole purpose of minimizing $\Vert Ax-b\Vert$ is to find the point on the subspace $ran A$, which is closest to $b$, which is only then really interesting, if $b$ is not a point in this subspace, right? $\endgroup$ Mar 10, 2020 at 6:36

2 Answers 2

1
$\begingroup$

The matrix equation given in the question tells us that $-r + Ax = b$ (in other words, $r = Ax - b$) and that $A^T r = 0$. Combining these two equations, we obtain $A^T (Ax - b) = 0$, which is the well known "normal equations" for solving a least squares problem.

One potential advantage of the equation given in the question is that if $A$ is sparse, then the coefficient matrix $$ \begin{bmatrix} -I & A \\ A^T & 0 \end{bmatrix} $$ is still sparse, whereas the matrix $A^T A$ appearing in the normal equations might be dense. Also, if $A$ has many more columns than rows, then $A^T A$ is a large dense matrix, which potentially takes up much more memory than $A$ itself.

$\endgroup$
0
$\begingroup$

In general, if $A x = b$ has an exact solution, then

\begin{align} x = A^{-1} b \end{align}

However, if $A x = b$ does not admit an exact solution, we can still find $x$ that minimizes the residual. Then,

\begin{align} r &= Ax - b \\ A^T r &= A^T A x - A^T b \\ 0 &= (A^T A)^{-1} A^T A x - (A^T A)^{-1} A^T b \end{align} the last line above follows from the fact that the residual is orthogonal to $A^T$ when the residual is minimized, i.e., in that case \begin{equation} A^T r = 0 \end{equation} This is known as the orthogonality principle. See https://en.wikipedia.org/wiki/Orthogonality_principle Therefore, \begin{align} x = (A^T A)^{-1} A^T b \end{align} The latter is the pseudo-inverse of $A$ times $b$.

In the matrix form proposed in your post, you wrote in a compact way the two key equations above, which are:

\begin{align} r&=Ax - b \\ A^T r&=0. \end{align} Due to the orthogonality principle, solving the two equations above is equivalent to solving \begin{align} \min_x r = Ax - b \end{align} and the solution is given by the pseudo-inverse. It is very convenient to rewrite the solution of an optimization problem as the solution of a set of linear equations, for which many known methods are available.

$\endgroup$

You must log in to answer this question.

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