It's easy to show that the solution to a least squares problem such as minimizing $\|Ax+b\|$ is $$x=(A^tA)^{-1}A^tb$$
But how can one minimize $$\sum_{i}\|A_ix+b_i\|$$?
In one of the passages of the book I'm reading (R.Szeliski. Computer vision, algorithms and applications), the author says that the point $P$ minimizing the following expression can be computed as a regular least squares problem:
$$\sum_j\|(I-v_j{v_j)}^t(P-c_j)\|^2$$
And then he directly gives the solution:
$$P=\left[\sum_j(I-v_j{v_j}^t)\right]^{-1}\left[\sum_j(I-v_j{v_j}^t)c_j\right]$$
I've been so far unable to understand how he reaches that conclusion...
I'll clarify that $v_j, c_j, P\in R^3$ in case you find it useful. So, as you can see, $(I-v_j{v_j}^t)(P-c_j)$ is the difference vector between $(P-c_j)$ and its projection on the line defined by $c_j+tv_j$.
Thanks a lot in advance!
Minimizing $\|Ax + b\|$ is, strictly speaking, not a least squares problem. It just happens to be equivalent to the least squares problem of minimizing $\|Ax + b\|^2$, because $x \mapsto x^2$ is increasing on $[0, \infty)$.
Minimizing $\sum_i \|Ax_i + b\|$ is however fundamentally different from minimizing $\sum_i \|Ax_i + b\|^2$. In the latter case, you are adding sums of squares, which gives you another sum of squares. Thus you get another least squares problem, which is what the author is referring to.
In the case of $\sum_i \|Ax_i + b\|$, you add square roots of sums of squares, and clearly you don't have $\sqrt{x^2 + y^2} + \sqrt{u^2 + v^2} = \sqrt{x^2 + y^2 + u^2 + v^2}$. That makes this a much harder problem.
Deriving the formula in the book can be done as follows, at least if I assume that the $v_j$ are unit vectors, which is necessary to make $I - v_jv_j^t$ a projection matrix.
For convenience, put $A_j = I - v_jv_j^t$ while noting that this is a symmetric, idempotent matrix.
Then we differentiate $\sum_j\|A_j(P-c_j)\|^2$ termwise to get the following equation for the critical point: $$ \sum_j A_j^tA_j(P-c_j) = 0. $$
Because of the special form of $A_j$ we have $A_j^tA_j = A_j$, which makes it possible to simplify and expand the equation to $$ \left(\sum_j A_j\right)P = \sum_j A_jc_j $$ which obviously leads to the desired result.