$\ell_1$ error minimization on $\ell_\infty$ ball

Question

Given vector $y \in \mathbb R^n$ and invertible matrix $B \in \mathbb R^{n \times n}$,

$$\begin{array}{ll} \underset{x \in \mathbb R^n}{\text{minimize}} & \lVert y - B x \rVert_1\\ \text{subject to} & \lVert x\rVert_\infty\le 1\end{array}$$

This could be tackled with linear programming. However, I wonder, is there a more efficient way to do this?

Answer 1

A possibility (HINT):

You can formulate your problem as \begin{align} &\min_x & & \underbrace{\left\|y-z \right\|_1}_{:=g(z)} + \underbrace{\delta_{C}(x)}_{:=f(x)} \\ & \mathrm{s.t.} & &Bx = z, \end{align} where the set $C = \left\{ x \in \mathbb{R}^n \mid \left\| x \right\|_{\infty} \leq 1 \right\}$.

Apply ADMM algorithm (not sure if it will be more efficient than LP)...