9
$\begingroup$

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)_+,$$

enter image description here

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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…

$\endgroup$
  • $\begingroup$ The Moreau paper is quite interesting. Looks like the solution to the problem is along those lines. For example, it follows that the soft-thresholding operator above is indeed a prox operator (without making any mention of the $\ell_1$-norm). Thanks once more. I'll find time to augment my question with these observations for non-french speaking audience. $\endgroup$ – dohmatob May 24 '16 at 13:03
  • 1
    $\begingroup$ @dohmatob but now I am curious to know what would qualify as an answer. At least for the soft thresholding function the "reverse definition" allows to quickly conclude that it is a proximal map… $\endgroup$ – Dirk May 24 '16 at 14:08
  • $\begingroup$ Ideally, I'd want a criterion which is "easy to check". Indeed the above criterion can be checked almost mechanically in 1D. In higher dimensions (may be I'm wrong) it is barren. Isn't the Moreau (in the paper you referenced) characterization "$p$ is a prox iff $p$ is nonexpansive and there exists convex $\varphi$ such that $p(z) \in \partial \varphi(z)\;\forall z$" more "efficient" ? Typically, the former condition comes almost free, by construction, for it is imposed, and the latter can be checked via some kind of integration. $\endgroup$ – dohmatob May 24 '16 at 15:51
  • $\begingroup$ Any more thoughts on this will be grately appreciated. I'm accepting your answer because (a) my question was not very precisely spelt down (b) your answer provides me sufficient fuel to continue the road with some light (notably the Moreau corollaries). Thanks once again $\endgroup$ – dohmatob May 24 '16 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.