# Composition of Proximal Operators

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.

• 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. – Michael Hardy Dec 13 '17 at 19:55
• Thank you for the changes – Rohit Arora Dec 13 '17 at 19:57
• 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. – Royi Mar 15 '18 at 21:19

## 1 Answer

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