Bounding the residual of a norm approximation problem

Question

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$?

Answer 1

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

Answer 2

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.