1
$\begingroup$

Consider a proximable function $f$ where the proximal operator is defined as follows, $$\operatorname{prox}_{\lambda f}(x) = \arg \min_z \frac{1}{2\lambda}\left\| z - x \right\|_2^2 + f(z)$$

$\lambda \geq 0$. With an additional constraint the problem is $$\arg \min_{z \ge 0} \frac{1}{2\lambda}\left\| z - x \right\|_2^2 + f(z)$$

which we can rewrite as $$\arg \min_z \frac{1}{2\lambda}\left\| z - x \right\|_2^2 + f(z) + I_{\left\{z \ge 0\right\}}(z)$$

$I_C(z)$ is an indicator function. The function $g$ defined as $$g(z) = I_{\left\{ {z \ge 0} \right\}}(z)$$ is also proximable and the resultant prox operator for $g$ is just a projection on the non-negative orthant. Combining all the above our unconstrained problem is defined as $$\arg \min_z \frac{1}{2\lambda} \|z - x\|_2^2 + f(z) + g(z)$$

Consider a toy example $f\left(x\right) = \|x\|_1$, then the solution of the constrained problem is obtained from component-wise thresholding, $z_i = \max(\max( |x_i| - \lambda, 0) \operatorname{sgn}(x_i),0)= \max\left(x_i-\lambda,0\right)$.

The solution seems like a composition of two proximal operators, $\operatorname{prox}_{g} \circ \operatorname{prox}_{\lambda f}$. Stated differently, it is also projection on the intersection of two sets, $\ell_1$-norm ball and the positive orthant. It is also similar to the idea of projected subgradient descent algorithm. Are there any general results/conditions where prox operator can be applied to composition of two proximable functions.

$\endgroup$
  • $\begingroup$ You certainly made your MathJax code a lot more complicated than it needs to be. I deleted 247 characters without changing anything that the reader sees. $\endgroup$ – Michael Hardy Dec 13 '17 at 19:55
  • $\begingroup$ Thank you for the changes $\endgroup$ – Rohit Arora Dec 13 '17 at 19:57
  • $\begingroup$ Do you need a closed form solution or a method to solve this? In general, there is no generalization of the Prox operator to a sum of 2 functions. $\endgroup$ – Royi Mar 15 '18 at 21:19
1
$\begingroup$

You are indeed right and can read about it in the paper - On Decomposing the Proximal Map.

Also have a look on the answers in Proximal Mapping of Least Squares with $ {L}_{1} $ and $ {L}_{2} $ Norm Terms Regularization (Similar to Elastic Net).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.