Is there a characterization of mappings $p : \mathbb R^n \rightarrow \mathbb R^n$ which are proximity operators (in the sense of Moreau) of l.s.c (extended) real-valued functions ? That is, given $p : \mathbb R^n \rightarrow \mathbb R^n$, under what sufficient conditions does there exist an extended-valued l.s.c convex function $g:\mathbb R^n \rightarrow (-\infty, +\infty]$ such that $$p(x) \equiv \mathrm{prox}_g(x) := \underset{z \in \mathbb R^n}{\text{argmin }}\frac{1}{2}\|z-x\|_2^2 + g(z) \;?$$

**N.B:** Of course it's necessary that $p$ be firmly-nonexpansive, and have other classical properties of prox operators.

**Motivation:** In regularization techniques for signal / image processing, one usually proposes to minimize an energy of the form $f(x) + g(x)$, where $x=x^*$ is the image to be recovered from noisy / corrupted measures, $f(x)$ is a *data fidelity* and measures the "fit" of the model, while $g(x)$ is a regularization term that imposes some structural constraints. For example, one can take $f(x) = \frac{1}{2}\|y-Ax\|_2^2$, under a additve Gaussian-noise assumption, where $y$ is the observed image and $A$ is a sensing linear operator, so that $y \approx Ax + \text{ noise}$, etc., etc.

A brilliant idea that has been proposed in *Social Sparsity!* is to impose the penalty $g$ only implicitly, by instead constructing its proximal operator $p(x)$, i.e by stating the intended shrinkage action of $g$ on the model coefficients $x_j$.

For a concrete example, think of a (fictional) world in which we didn't know about the $\ell_1$ norm, but instead decided to invent the Lasso by stating that the prox of the (unknown) $\ell_1$ penalty should shrink the coefficients according to the *soft-thresholder*
$$(p(x))_j = st_{\lambda}(x_j) = sign(x_j)(|x_j| - \lambda)_+,$$

where $\lambda > 0$ is a regularization parameter and $sign(x_j): = -sign(-x_j) = 1$ if $ x_j > 0$ and $0$ else. Note that the above prox would correspond to a penalty $g(x) = \lambda \|x\|_1$, and acts component-wise only because we're assuming (in this example) a separable penalty.

The question is then: *How to show that $st_{\lambda}$ actually corresponds to the proximal operator of some penalty function.*