When is a mapping the proximity operator of some convex function?

The paper

On Decomposing the Proximal Map, Yaoliang Yu, NIPS, 2013

states that in

Jean J. Moreau. Proximité et dualtité dans un espace Hilbertien. Bulletin de la Société Mathématique de France, 93:273–299, 1965.

it is shown that every non-expansive mapping for $\newcommand{\RR}{\mathbb{R}}\RR$ to $\RR$ that is also a subgradient of a proper, convex, lsc function in indeed a proximal map.

In higher dimensions this is not true anymore (and the former paper gives a counterexample).

Also, I am not really sure, what kind of answer you would satisfying. Here's a charcterization: A map $P:\RR^n\to\RR^n$ is a proximal map, if and only if it's (probably set-valued) inverse minus the identity is a subgradient of a proper, convex, lsc function. In other words: If and only if $P^{-1}-I$ is maximally monotone. But well, this is basically the definition read backwards…

You may be interested in the characterization of proximity operators (of convex or nonconvex functions) provided in the paper https://hal.inria.fr/hal-01835101

In fact, the Moreau paper (Corollary 10.c) shows that $f: \mathcal{H} \to \mathcal{H}$ is the proximal map associated to some convex lsc $\varphi: \mathcal{H} \to \mathbb{R}$ if, and only if, the following two conditions hold:

• $f$ is the subdifferential of some convex lsc function $\psi: \mathcal{H} \to \mathbb{R} \cup \{+\infty\}$;
• $f$ is non-expansive

Here $\mathcal{H}$ is any Hilbert space, finite or infinite dimensional.

To answer your question, one also needs to consider the case where $\varphi$ may be nonconvex. In https://hal.inria.fr/hal-01835101 it is shown (Theorem 1) that: $f: \mathcal{Y} \subset \mathcal{H} \to \mathcal{H}$ is the proximal map associated to some (possibly nonconvex) $\varphi: \mathcal{H} \to \mathbb{R}$ if, and only if, $f$ is the subdifferential of some convex lsc function $\psi : \mathcal{H} \to \mathbb{R} \cup \{+\infty\}$.

In practice, it may not always look straightforward to check that $f$ is a subdifferential (this is related to notions such as cyclic monotonicity). Luckily this is easier when $f$ is $C^1$ (Theorem 2): when $f$ is $C^1$, it is the proximity operator of some $\varphi$ if, and only if, its differential $Df(y)$ is symmetric positive semi-definite.

The case of social sparsity shrinkage operators is precisely considered in Section 1.4: using Theorem 2, it is shown (Corollary 5) that a family of social shrinkage operators are not proximity operators, except in classical cases where they match group-sparsity shrinkage with disjoint groups.

As far as I know, Moreau fully characterizes proximity operators of convex $\varphi$ are fully characterized by Moreau -a function f