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

Question

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.

Answer 1

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

Answer 2

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…