Minimize sum of Least Squares

Question

If xi minimizes ||Ax-bi||^2, how do I solve minimize ||Ax-b1||^2 + ... ||Ax-bk||^2 in terms of x1 through xk? I am looking for some direction.

Answer 1

Note that all problems are convex.

If $x_i$ minimizes $x \mapsto \|Ax-b_i\|^2$, then $A^T(Ax_i - b_i) = 0$.

The gradient of $x \mapsto \sum_i \|Ax-b_i\|^2$ is given by $\sum_i A^T(Ax - b_i) = nA^TAx-A^T \sum_i b_i$, hence if we set $\hat{x}= {1 \over n} \sum_i x_i$, we have $\sum_i A^T(A\hat{x} - b_i) = 0$, hence $\hat{x}$ solves the problem (since the problem is convex).