Projection in $\ell_1$ norm onto linear subspace of $\mathbb{R}^n$. In the context of $\mathbb{R}^n$, fix a linear subspace $\mathcal{U}$ or arbitrary dimension $r \leq n$ and some vector $\mathbf{x} \in \mathbb{R}^n$. 
What is the most efficient way to compute the projection of $\mathbf{x}$ onto $\mathcal{U}$ in $\ell_1$, that is, how had one ought to solve the optimization problem:
$\mathbf{u}^* = \min_{\mathbf{u} \in \mathcal{U}} ||\mathbf{u} - \mathbf{x}||_1$
I have a hard time believing this is not a well understood problem but I am having difficulty with Google.
One could clearly formulate this as a linear program, but I am primarily concerned with high dimensional problems for $n$ large. Is there a more efficient way?
 A: Well, $\displaystyle\min_{\mathbf{u}\in\mathcal{U}}||\mathbf{u}-\mathbf{x}||_1=\min\{r\in\mathbb{R}_{\geqslant 0} : \mathcal{U}\cap B_1(\mathbf{x},r)\neq\emptyset\}$, where
$$B_1(\mathbf{x},r)=\{\mathbf{y}\in\mathbb{R}^n : ||\mathbf{y}-\mathbf{x}||_1\leqslant r\}$$
is the closed $l_1$-ball with center $\mathbf{x}$ and radius $r$. It is the convex hull of
$$E_1(\mathbf{x},r)=\{\mathbf{x}\pm r\mathbf{e}_k : 1 \leqslant k \leqslant n\},$$
where $(\mathbf{e}_1,\ldots,\mathbf{e}_n)$ is the standard basis of $\mathbb{R}^n$. It follows that
$$\displaystyle\min_{\mathbf{u}\in\mathcal{U}}||\mathbf{u}-\mathbf{x}||_1=r^\ast\implies\mathcal{U}\cap E_1(\mathbf{x},r^\ast)\neq\emptyset,$$
the minimum is attained at any (not necessarily unique) element $\mathbf{u}^\ast$ of the last set, and the convex hull of all such $\mathbf{u}^\ast$ is the solution to the original problem.
So the whole problem reduces to finding the minimum of at most $n$ real numbers
$$r_k = \inf\{|r| : \mathbf{x}+r\mathbf{e}_k\in\mathcal{U}\},\quad 1\leqslant k\leqslant n$$
(with $\inf\ \emptyset$ considered to be $+\infty$).
