1

Given a norm approximation problem $$\text{minimize}\ \ \lVert Ax-b\rVert$$ and its optimal solution vector $x^*$, it is quite easy to show that $0\leq\lVert Ax^*-b\rVert\leq\lVert b\rVert$.

Is it also true that $\lVert Ax^*-b\rVert<\lVert b\rVert$?

Filippo Bistaffa
  • 197
  • 8

2 Answers2

0

No. Suppose that $A$ does not have full rank, and $b$ does not lie in the image of $A$. Then $0$ is the closest point in the range of $A$ to $b$. For a concrete example, take $$ A = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}, \qquad B = \begin{pmatrix} 0 \\ 1 \end{pmatrix}. $$ Then $$ \lVert Ax - b \rVert^2 = x_1^2 + 1, $$ so the minimum is achieved at $x_1=0$, the value of $x_2$ is unimportant, and $$ \lVert A(0,x_2) - b \rVert^2 = \lVert 0-b \rVert^2 = \lVert b \rVert^2. $$

In general, let the range of $A$ be $S$. Either $b$ is in $S$ or it isn't. If it is, the minimum is zero (we can find $x$ so that $Ax=b$, that's the point of the definition of range).

So suppose $b$ is not in the range of $A$. This is the same situation as minimising the distance between a point and a plane, and the same idea works: $b$ has an orthogonal decomposition into $P_S(b)$ and $b-P_S(b)$, where $P_S$ is the orthogonal projection onto $S$. $P_S(b)$ is the closest point in $S$ to $b$. Then $$ \min_{x}\lVert Ax-b \rVert^2 = \lVert b-P_S(b) \rVert^2 = \lVert b \rVert^2 -\lVert P_S(b) \rVert^2, $$ so equality occurs if and only if $P_S(b)=0$.

Chappers
  • 67,606
  • What if we know that A has a full rank? – Filippo Bistaffa Apr 18 '17 at 20:57
  • Then $b$ lies in the range of $A$, so you can find $x^$ with $Ax^=b$ and the minimum is zero. – Chappers Apr 18 '17 at 21:53
  • Not necessarily. It can have full column rank but not full row rank. – Michael Grant Apr 18 '17 at 23:40
  • Okay, either $b$ is in the image of $A$ or it isn't. If it is, you can find $x^*$ with $Ax=b$. If not, the span of the rows of $A$ is a subspace $S$, and the closest point is the orthogonal projection $P_S(b)$ of $b$ onto $S$, the minimum then being $\lVert b-P_S(b) \rVert$. By the triangle inequality, this is at most $\lVert b \rVert$, and equal to it if and only if $P_S(b)=0$. – Chappers Apr 19 '17 at 00:06
  • So, assuming that $A$ has full column rank, and $b$ is not in the image of A, if $P_S(b) \neq 0$, then $\lVert Ax^*-b\rVert<\lVert b\rVert$? – Filippo Bistaffa Apr 19 '17 at 08:07
  • It's true for any $A$ if $P_S(b) \neq 0$, by essentially by Pythagoras. – Chappers Apr 19 '17 at 13:31
  • Ok thanks. Maybe you can include the discussion in these comments in your original answer, and then I can accept it. – Filippo Bistaffa Apr 19 '17 at 15:16
0

No. Not if $A$ has non-trivial kernel. Indeed, by the orthogonality property of least-squares solutions, the residue $Ax^* - b$ lives in the orthogonal complement of the image of $A$. Thus, for any other point $x$, we have by Pythagoras's theorem,

$$ \begin{split} \|Ax-b\|_2^2 &= \|A(x-x^*) + Ax^* -b\|^2_2 = \|A(x-x^*)\|^2_2 + \|Ax^*-b\|_2^2\\ & = \|Ax^*-b\|_2^2, \text{if }x - x^* \in \ker A. \end{split} $$

Conclude.

dohmatob
  • 9,535