We are given a matrix $A$ of full columns rank and a vector $b$ of appropriate sizes and want so solve the problem $\min_x || Ax-b||_2$. I know that the best solution is given by $x^\star=A^+b$ where $A^+$ denotes the More-Penrose-Inverse.
My question is now the following: Can we say anything about how large the norm will still be, something like $||Ax^*-b||_2 \leq d$ or $||Ax^*-b||\geq d$ for some constant d?
I tried plugging in the solution, but was unable to simplify the term. Does anyone know any common results?
No such bound is possible. Consider $A=\left(\begin{matrix}1 & 0\\ 0 & 1\\ 0 & 0\end{matrix}\right)$ and $b=\left(\begin{matrix}0\\ 0\\ b'\end{matrix}\right)$ where $b'\in\mathbb{R}$. The solution to the optimization problem is given by $x^\star= \left(\begin{matrix}0\\ 0\end{matrix}\right)$ yet $\|Ax^\star-b\|_2 = |b'|$ which is arbitrary in $\mathbb{R}_+$.
Actually the same argument holds with the even simpler example using $A=\left(\begin{matrix}1 \\ 0\end{matrix}\right)$, $b=\left(\begin{matrix}0\\ b'\end{matrix}\right)$, and $x^\star=0$.