# Proximal Operator / Mapping of $g \left( x \right) = {\left\| x \right\|}_{1}$ (${L}_{1}$ Norm) in the Complex Domain

The $\operatorname{Prox}_{g \left( \cdot \right)}$ operator is given by:

$$\operatorname{Prox}_{\lambda g \left( \cdot \right)} \left( x \right) = \arg \min_{u} \left\{ g \left( u \right) + \frac{1}{2 \lambda} {\left\| u - x \right\|}^{2} \right\}$$

For $g \left( x \right) = {\left\| x \right\|}_{1}$ in the ${\mathbb{R}}^{n}$ the is given by:

$$\operatorname{Prox}_{\lambda {\left\| \cdot \right\|}_{1}} = \begin{cases} {x}_{i} - \lambda & \text{ if } {x}_{i} \geq \lambda \\ 0 & \text{ if } \left| {x}_{i} \right| \leq \lambda \\ {x}_{i} + \lambda & \text{ if } {x}_{i} \leq -\lambda \\ \end{cases}$$

My question is, what would be the result if the domain is ${\mathbb{C}}^{n}$?

Namely:

$$\operatorname{Prox}_{\lambda {\left\| \cdot \right\|}_{1}} \left( x \right) = \arg \min_{u} \left\{ {\left\| x \right\|}_{1} + \frac{1}{2 \lambda} {\left\| u - x \right\|}^{2} \right\}, \; u ,x \in {\mathbb{C}}^{n}$$

Thank You.

• If you were to guess what it is---seriously, just think about it visually, and take a wild guess---what would you say? I'll bet you get it right. Commented Jan 6, 2017 at 15:02
• Another hint: try to write a formula for the real-valued prox function that doesn't require three separate cases. How would you do that? Commented Jan 6, 2017 at 15:04
• @MichaelGrant, My bet is that the angle will be the same and the magnitude will "Shrinked" (Soft Threshold).
– Royi
Commented Jan 6, 2017 at 15:56
• That is exactly right. Commented Jan 6, 2017 at 15:58
• The issue is how to derive it form the definition. Yet it would require knowing the Sub Gradient of ${\left\| x \right\|}_{1}$ on the Complex Domain. Which means, is it still the Complex Sign Function? How can I prove that?
– Royi
Commented Jan 6, 2017 at 16:03

Let $\phi(u,x) = \|u\|_1 + {1 \over 2\lambda} \|x-u\|_2^2$. With a slight abuse of notation, note that $\phi(u,x) = \sum_k \phi(u_k,x_k)$, so we may as well assume that $u,x \in \mathbb{C}$.

If $x=0$, we see that $\operatorname{prox}_{\lambda {|\cdot|}} (x) = 0$, so assume $x \neq 0$.

Note that if $|\theta|=1$, then $\phi(u,x) = \phi(\theta u, \theta x)$ and also $\phi(u,x) \ge \phi(\operatorname{re} u, \operatorname{re} x)$.

In particular, $\phi(u,x) = \phi({\bar{x} \over |x|} u, |x|) \ge \phi(\operatorname{re}({\bar{x} \over |x|} u), |x|)$, from which we see that (i) we need only optimise over real $u$ and (ii) $\operatorname{prox}_{\lambda {|\cdot|}} (x) = {|x| \over \bar{x}} \operatorname{prox}_{\lambda {|\cdot|}} (|x|)$, where the latter is computed over a real domain (we have $\operatorname{prox}_{\lambda {|\cdot|}} (|x|) = \max(0,|x|-\lambda)$).

Notes:

(i) ${|x| \over \bar{x}} = { x \over |x| }$.

(ii) The real (one or higher dimension) problem $\min_u \|u\|_1 + {1 \over 2 \lambda } \|x-u\|_2^2$ has a nice solution via a minor extension of the von Neumann mimimax theorem. We have $\|u\|_1 =\max_{\|h\|_\infty \le 1} \langle h, u \rangle$ and the problem can be written as $\min_u \max_{\|h\|_\infty \le 1} \langle h, u \rangle + {1 \over 2 \lambda } \|x-u\|_2^2$. Applying the aforementioned theorem (with a minor extension to deal with the non compact domain for $u$) we have $\min_u \max_{\|h\|_\infty \le 1} \langle h, u \rangle + {1 \over 2 \lambda } \|x-u\|^2 = \max_{\|h\|_\infty \le 1} \min_u \langle h, u \rangle + {1 \over 2 \lambda } \|x-u\|_2^2$ and solving the inner quadratic problem gives $\min_u \max_{\|h\|_\infty \le 1} \langle h, u \rangle + {1 \over 2 \lambda } \|x-u\|_2^2 = \max_{\|h\|_\infty \le 1} \langle h, x \rangle - {\lambda \over 2} \|h\|_2^2$ (with $\lambda h - (x-u) = 0$).

This is separable, and reduces to solving $\max_{|h_k| \le 1} h_k x_k - {\lambda \over 2} h_k^2$, which has solution $h_k = \operatorname{sgn} x_k \min(1,{|x_k| \over \lambda})$, and substituting into $u_k= x_k-\lambda h_k$ gives the solution $u_k=\operatorname{sgn} x_k \max(0,|x_k|-\lambda)$

• Shouldn't it be, the solution I got (Only by Geometry) to the least, $\frac{x}{\left| x \right|} \max \left( 0, \left| x \right| - \lambda \right)$? I +1 your answer. Thank You.
– Royi
Commented Jan 7, 2017 at 11:12
• @Royi: Let me check, I could easily have made a mistake. Commented Jan 7, 2017 at 21:43
• @Royi: If $x \neq 0$ we have ${x \over |x|} = {|x| \over \overline{x}}$. Commented Jan 7, 2017 at 21:46
• @Royi: All the above are the same ${x \over |x|} = {|x| \over \overline{x}} = \overline{({|x| \over x})}$. Use whatever formula you are comfortable with, they are all equivalent. Commented Jan 8, 2017 at 6:38
• Do we agree that $\frac{x}{\left| x \right|}$ is a complex number with its magnitude equals to 1 (On the Unit Circle)? Also do we agree that $\frac{x}{\left| x \right|} = {\left( \frac{\left| x \right|}{x} \right)}^{-1}$?
– Royi
Commented Jan 8, 2017 at 6:41