On Decomposing the Proximal Map
The proximal map is the key step in gradient-type algorithms, which have become prevalent in large-scale high-dimensional problems. For simple functions this proximal map is available in closed-form while for more complicated functions it can become highly nontrivial. Motivated by the need of combining regularizers to simultaneously induce different types of structures, this paper initiates a systematic investigation of when the proximal map of a sum of functions decomposes into the composition of the proximal maps of the individual summands.
We not only unify a few known results scattered in the literature but also discover several new decompositions obtained almost effortlessly from our theory.
The paper deals with an interesting theoretical 
      question concerning the proximity operator. It investigates when the 
      proximity of the sum of two convex functions decomposes into the 
      composition of the corresponding proximity operators. The problem is 
      interesting since in the applications there is a growing interest in 
      building complex regularizers by adding several simple terms. They 
      pursues a quite complete study. After proving a simple sufficient 
      condition (Theorem 1), they gives the main result of the paper (Theorem 
      4): it is a complete characterization of the property (for a function) of 
      being radial versus the property of being ``well-coupled'' with positively 
      homogeneous functions (where well-coupled means that the prox of the sum 
      of the couple decomposes into the composition of the two individual prox 
      map). They also consider the case of polyhedral gauge functions, deriving 
      a sufficient condition which is expressed by means of a cone invariance 
      property. Examples are provided which show several prox-decomposition 
      results, recovering known facts (in a simpler way) but also proving new 
      ones. The value of the paper is mainly on the theoretical side. It 
      sheds light on the mechanism of composing proximity operators and unifies 
      several particular results that were spread in the literature. The article 
      is well written and technically sound. The only fault I see is that 
      perhaps some times is not completely rigorous as I explain in the 
      following. TYPOS, SMALL CORRECTIONS AND SUGGESTIONS: -- 
      Before formula (4), I would add the sentence that the Moreau envelope 
      $M_f$ is Frechet differentiable and $\nabla M_f = P_{f^*}$. -- 
      after formula (5), replace ``$f \circ g$ denotes the function 
      composition'' with ``$P_f \circ P_g$ denotes the mapping composition''. 
      -- For the formula $P_{f+g} = (P_{2 f}^{-1} + P_{2 g}^{-1})^{-1} 
      \circ 2 Id$ to be valid, one needs to guarantee in some way that $\partial 
      (f + g) = \partial f + \partial g$ --- for instance assuming 0 $\in 
      sri(dom f - dom g)$. -- The proof of Proposition 1, might be more 
      direct if one relies on Proposition 2.4 in [13]. -- The equation 
      at the end of Example 1, expreses actually the firmly non-expansivity of 
      the composition $P_f \circ P_g$, which is a property satisfied by any 
      proximity operators. This should be mentioned somewhere. I find the 
      reference to [11, Eq. (5.3)] a little bit vague. For completeness one can 
      refer more explicitly to Def 2.3 and Lemma 2.4 in [3]. -- In 
      section 3.1, the condition $dom f \cap dom g$ non void should be assumed. 
      It could be stated at the beginning of the section. -- Statement 
      of Proposition 2. The set $K_f$ is clearly a cone. I am not sure that it 
      is also convex. Again, note that $\partial g_1 (x) + \partial g_2(x)$ in 
      general is only strictly included in $\partial (g_1 + g_2)(x)$. However if 
      e.g.~one of the $g_i$ is finite on the whole space, then $g_i \in K_f 
      \implies g_1 + g_2 \in K_f$. This is the way this proposition is used 
      later in Corollary 4. -- The result stated in Proposition 3 is 
      already in Moreau[11]. Thus the proof could be omitted, just refer to the 
      article. -- The first equation in section 3.3 is not completely 
      rigorous. What is $g^\prime(s x)$? the directional derivative or a 
      subgradient? Moreover $\partial g(s x)$ is a subset, so what does it mean 
      $\langle \partial g(s x), x \rangle$? -- Before the sufficient 
      condition (15), I would add that $\partial k(x) = \{ a_j \vert j \in J, x 
      \in K_j\}$. This would help to understand why the sufficient condition in 
      Theorem 1 becomes (15). MORE CRITICAL POINTS: -- 
      Formula (6) would require that $\partial (f+ g) = \partial f + \partial 
      g$. However the condition in Theorem 1 is sufficient even if one only 
      assumes $dom f \cap dom g$ non void. Just replace (6) with $P_{f + g}(y) - 
      y + \partial (f+g) (P_{f+g}(y)) \ni 0$. Then use (9), the sufficient 
      condition, and the fact that $\partial f (P_f(P_g(y))) + \partial 
      g(P_f(P_g(y))) \subset \partial (f + g) (P_f (P_g(y)))$. -- I 
      cannot see the reason for the emphasis put on Proposition 4 and the need 
      to derive it by means of the (not so simple) ``trick'' discussed in Remark 
      3. Indeed Proposition 4 is a quite trivial result that follows directly 
      from the changing formula for prox (see e.g.~Proximal Spitting Methods in 
      Signal Processing by Combettes and Pesquet) and Proposition 3. Note also 
      that the hypothesis $0 \in dom f$ should be added.