Let the least square problem be $Ax=b$. If the vector $v$ satisfies $A^*v=0$, why does adding a multiple of $v$ to the right hand side $b$ does not change the solution, e.g., $Ax=b+tv$, for $t$ a constant?
Thanks.
Let the least square problem be $Ax=b$. If the vector $v$ satisfies $A^*v=0$, why does adding a multiple of $v$ to the right hand side $b$ does not change the solution, e.g., $Ax=b+tv$, for $t$ a constant?
Thanks.
The least squares problem is to minimize $\phi_b(x) = \frac{1}{2}\|Ax-b\|_2^2$. $\phi$ is a smooth convex function, so the first order optimality conditions are necessary and sufficient.
A quick calculation shows that $\frac{\partial \phi_b(x)}{\partial x} = x^TA^T A - b^T A = (A^T(Ax-b))^T$, hence $x$ is a solution iff we have $A^T(Ax-b) = 0$.
It follows that if $x$ is a solution, and $A^T v = 0$, then $A^T(Ax-b+ t v) = 0$ also, from which it follows that $x$ is a solution to the problem of minimizing $\phi_{b+t v}$.
Hence any $x$ that solves the least squares problem with rhs $b$ will also solve the least squares problem with rhs $b+t v$.