I'm trying to figure out if there's a way to efficiently compute the proximal operator of $l1$ norm, constrained by the $l2$ unit ball.
Let $$f(\mathbf{x}) = \begin{cases} &\|\mathbf{x}\|_1, &\|\mathbf{x}\|_2\leq 1\\ & \inf, &\text{else} \end{cases}$$ Then the problem formulation is $$\text{prox}_f(\mathbf{x})=\text{argmin}_{\|\mathbf{u}\|_2\leq 1}\;\|\mathbf{u}\|_1+\frac{1}{2}\|\mathbf{u}-\mathbf{x}\|_2^2=\text{argmin}_{\|\mathbf{u}\|_2\leq 1}\;\|\mathbf{u}\|_1+\frac{1}{2}\|\mathbf{u}\|_2^2-\mathbf{x}^T\mathbf{u}$$
We notice that the two separable $\mathbf{u}$ terms are minimized at $\mathbf{0}$ while $-\mathbf{x}^T\mathbf{u}$ would be minimized when $\mathbf{u}=\frac{\mathbf{x}}{\|\mathbf{x}\|_2}$. I'm trying to figure out how we can balance between the two, clearly depending on the norm value of $\mathbf{x}$. Maybe based on some sort of root search, similar to the prox of projecting onto $l1$ ball?
What I think that could work, based on the idea to use duality / conjugate, is the following: calculate $f^*(\mathbf{y})$, then $\text{prox}_{f^*}$, and use Moreau decomposition $\text{prox}_{f}(\mathbf{x}) + \text{prox}_{f^*}(\mathbf{x}) = \mathbf{x}$ to get the desired result.
So far I could calculate $f^*(\mathbf{y})$, but still no luck with $\text{prox}_{f^*}$.
$$f^*(\mathbf{y}) = \max_{\|\mathbf{x}\|_2 \leq 1} \mathbf{x}^T\mathbf{y}-\|\mathbf{x}\|_1=\max_{\|\mathbf{x}\|_2 \leq 1} \mathbf{x}^T\mathbf{y}-\max_{\|\mathbf{u}\|_{\infty} \leq 1}\mathbf{x}^T\mathbf{u}=\max_{\|\mathbf{x}\|_2 \leq 1} \min_{\|\mathbf{u}\|_{\infty} \leq 1}\mathbf{x}^T\mathbf{y}-\mathbf{x}^T\mathbf{u},$$ and since the expression above is convex in $\mathbf{u}$, concave in $\mathbf{x}$, we can change the order of optimization to get $$f^*(\mathbf{y})= \min_{\|\mathbf{u}\|_{\infty} \leq 1}\max_{\|\mathbf{x}\|_2 \leq 1}\mathbf{x}^T\mathbf{y}-\mathbf{x}^T\mathbf{u}\overset{\mathbf{x}=\frac{\mathbf{y-u}}{\|\mathbf{y-u}\|_2}}=\min_{\|\mathbf{u}\|_{\infty} \leq 1}\|\mathbf{y-u}\|_2=\|[\mathbf{|y|-1}]_+\|_2.$$
With $[\mathbf{|y|-1}]_+=\max\{|y_i|-1,0\}$ for every component $i=1,\dots,n$. However I got stuck from here on, and was not able to calculate $\text{prox}_{f^*}(\mathbf{y})=\text{argmin}_{\mathbf{u}\in\mathbb{R}^n} \|[\mathbf{|u|-1}]_+\|_2 + \frac{1}{2}\|\mathbf{u-y}\|_2^2$.
Ideas anyone? I assume the solution will require some 1-D root search, similar to the one used in the projection onto $l1$ ball. But any linear complexity algorithm is fine.