L-infinity-norm regularized proximity problem I have a question:
$$\min_x {1\over 2} \|x-t\|^2 + \lambda \|x\|_\infty$$
where $t, \lambda$ are given constant.
I think this may be a classic problem? However, I didn't find closed form of its solution. What I tried is as follows.
I tried transforming it into a constrainted version:
$$\min_{x,s} {1\over 2} \|x-t\|^2 + \lambda s\\
s.t.\ x_i\leq s,\ x_i\geq -s,\ \forall i=1,2,...,p
$$
where $p$ is the dimensionality of $x$. Then get the Lagrangian:
$$L(x,s,a,b)={1\over 2} \|x-t\|^2 + \lambda s+\sum_{i=1}^pa_i(x_i-s)+\sum_{i=1}^pb_i(-x_i-s).$$
I tried to derive something from the KKT conditions, but that seems to be a total mess, making me doubt this way.
 A: This is indeed a classic problem. Recall the more general problem of computing the prox operator of an lsc convex function $f$, i.e.,
\begin{equation*}
\text{prox}_f(y) := \operatorname{argmin}\quad \tfrac12\|x-y\|^2 + f(x).
\end{equation*}
For this prox operator, we have the well-known Moreau decomposition
\begin{equation*}
\text{Id} = \text{prox}_f + \text{prox}_{f^*},
\end{equation*}
where $f^*$ denotes the Fenchel conjugate of $f$. In your case, $f(x)=\lambda \|x\|_{\infty}$, whose conjugate is the indicator function for the constraint $\|x\|_1 \le \lambda$. Thus, you can alternatively solve the optimization problem
\begin{equation*}
\min\quad \tfrac12\|x-y\|^2\quad\text{s.t.}~~\|x\|_1 \le \lambda.
\end{equation*}
This is the projection onto the $\ell_1$-ball, which is an extensively well-studied problem. I would recommend this paper by L. Condat, which gives a more recent summary of this classic problem (dates to the 1950s), and to a few existing methods while providing some additional context (also, you can find C code at this link from L. Condat's webpage).
