0
$\begingroup$

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.

  • 0
    Caught me for a while too...2012-11-02

1 Answers 1

3

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