2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Commented Jan 6, 2017 at 15:02
  • $\begingroup$ 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? $\endgroup$ Commented Jan 6, 2017 at 15:04
  • $\begingroup$ @MichaelGrant, My bet is that the angle will be the same and the magnitude will "Shrinked" (Soft Threshold). $\endgroup$
    – Royi
    Commented Jan 6, 2017 at 15:56
  • $\begingroup$ That is exactly right. $\endgroup$ Commented Jan 6, 2017 at 15:58
  • $\begingroup$ 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? $\endgroup$
    – Royi
    Commented Jan 6, 2017 at 16:03

1 Answer 1

2
$\begingroup$

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)$

$\endgroup$
9
  • 1
    $\begingroup$ 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. $\endgroup$
    – Royi
    Commented Jan 7, 2017 at 11:12
  • $\begingroup$ @Royi: Let me check, I could easily have made a mistake. $\endgroup$
    – copper.hat
    Commented Jan 7, 2017 at 21:43
  • $\begingroup$ @Royi: If $x \neq 0$ we have ${x \over |x|} = {|x| \over \overline{x}}$. $\endgroup$
    – copper.hat
    Commented Jan 7, 2017 at 21:46
  • $\begingroup$ @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. $\endgroup$
    – copper.hat
    Commented Jan 8, 2017 at 6:38
  • $\begingroup$ 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} $? $\endgroup$
    – Royi
    Commented Jan 8, 2017 at 6:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .