min : sum of two L2 norms

Question

Is there a closed-form solution of the:

$$\min_x \| Ax - b1 \|_2 + \| Ax - b2 \|_2$$

where A = m*n matrix and b1,b2 are m length vectors.

Answer 1

If we let $P$ be the projection matrix on the span of $A$. We can prove that the minimum can be obtain only when $Ax$ is on the segment between $Pb_1$ and $Pb_2$ (I leave that to you but I can help if needed). Then any point on that segment can be written $\lambda Pb_1+(1-\lambda)Pb_2$ with $\lambda\in[0,1]$, then \begin{align*} \min_x \lVert Ax-b_1 \rVert + \lVert Ax-b_2 \rVert&=\min_{\lambda\in[0,1]} \lVert \lambda Pb_1+(1-\lambda)Pb_2-b_1 \rVert + \lVert \lambda Pb_1+(1-\lambda)Pb_2-b_2 \rVert\\ \end{align*}

if we write \begin{align*} \lVert \lambda Pb_1+(1-\lambda)Pb_2-b_1 \rVert &= \lVert \lambda Pb_1+(1-\lambda)Pb_2-(P+I-P)b_1 \rVert\\ &=\lVert (\lambda-1) Pb_1+(1-\lambda)Pb_2-(I-P)b_1 \rVert\\ &=\sqrt{\lVert (\lambda-1) Pb_1+(1-\lambda)Pb_2 \rVert^2+\lVert (I-P)b_1\rVert^2}\\ &=\sqrt{(1-\lambda)^2\lVert P(b_1-b_2)\rVert^2+\lVert (I-P)b_1\rVert^2} \end{align*} where the third line comes from the fact that $I-P$ is the projection on the space orthogonal to $P$, the same reasoning can be applied to the second term to get \begin{align*} \lVert \lambda Pb_1+(1-\lambda)Pb_2-b_2 \rVert&=\sqrt{\lambda^2\lVert P(b_1-b_2)\rVert^2+\lVert (I-P)b_2\rVert^2} \end{align*} in other term, if we let $a=\lVert P(b_1-b_2)\rVert^2$, $c_1=\lVert (I-P)b_1\rVert^2$ and $c_2=\lVert (I-P)b_2\rVert^2$, then we search for the minimum over $\lambda\in[0,1]$ of $\sqrt{a\lambda^2+c_1}+\sqrt{a(1-\lambda)^2+c_2}$ the first derivative is $\frac{a\lambda}{\sqrt{a\lambda^2+c_1}}-\frac{a(1-\lambda)}{\sqrt{a(1-\lambda)^2+c_2}}$ , setting it to $0$ gives \begin{align*} &\lambda^2 (a(1-\lambda)^2+c_2)=(1-\lambda)^2(a\lambda^2+c_1)\\ \Leftrightarrow & \lambda^2 = \frac{c_1}{c_1+c_2} \end{align*} and since we want $\lambda\in[0,1]$, then $\lambda=\sqrt{\frac{c_1}{c_1+c_2}}$.