Bounding the residual of a norm approximation problem 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$?
 A: 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$.
A: 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.
