Proximal Operator for $g\left(x\right)=\mu{\left\|x\right\|}_1 + I_{\left\|x\right\|_2 \leq 1} \left(x\right)$ ($L_1$ Norm and Unit Ball Constraint)

Question

I am wondering if there is a simple closed form solution to the constrained proximal mapping problem:

$$ \operatorname*{argmin}_{\beta: \|\beta\|_2 \leq 1} \frac{1}{2\mu }\|X - \beta\|_2^2 + \|\beta\|_1,$$ where $\|a\|_1 = \sum_{i=1}^p |a_i|$. Intuitively, I would think that the solution is the projection of the unconstrained solution (i.e., soft thresholded solution) onto the unit sphere, but I am having difficulty proving this. Perhaps my intuition is wrong here, or I am overlooking a simple property of proximal operators.

Any tips on a direction for proof or papers for reference would be appreciated.

Answer 1

The problem is given by:

$$\begin{aligned} \arg \min_{x} \quad & \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \mu {\left\| x \right\|}_{1} \\ \text{subject to} \quad & {\left\| x \right\|}_{2} \leq 1 \end{aligned}$$

Which is equivalent to

$$\begin{aligned} \arg \min_{x} \quad & \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \mu {\left\| x \right\|}_{1} \\ \text{subject to} \quad & {\left\| x \right\|}_{2}^{2} \leq 1 \end{aligned}$$

The Lagrangian is given by:

$$ L \left( x, \lambda \right) = \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \mu {\left\| x \right\|}_{1} + \lambda \left( {x}^{T} x - 1 \right) $$

With similar reasoning to the solution of Orthogonal Projection onto the $ {L}_{2} $ Unit Ball and derivation of the Proximal Operator of the $ {L}_{1} $ Norm one could conclude that (By examining the case $ \lambda \neq 0 $ and the case $ \lambda = 0 $):

1. If the norm of $ y $ after the soft thresholding is larger than 1 then one should apply the projection onto the $ {L}_{2} $ Unit Ball.
2. If the norm of $ y $ before or after the soft thresholding is smaller or equal to 1 then then one should apply only the Soft Thresholding.

Hence the solution is given by:

$$ x = \frac{ \operatorname{sign} \left( y \right ) {\left( \left| y \right| - \mu \right)}_{+} }{ \max \left( 1, \operatorname{sign} \left( y \right ) {\left( \left| y \right| - \mu \right)}_{+} \right) } = \frac{ \mathcal{S}_{\mu} \left( y \right) }{ \max \left( 1, \mathcal{S}_{\mu} \left( y \right) \right) } $$

Where $ \mathcal{S}_{\mu} \left( \cdot \right) $ is the Soft Threshold operator with parameter $ \mu $ and $ {\left( \cdot \right)}_{+} $ denotes the positive part.

To verify the result I implemented it in MATALB and verified it against CVX.
The code is available at my StackExchange Mathematics Q2057347 GitHub Repository.