Relations, resolvents and the proximal operator

Relations and resolvents

A relation F on \mathbb{R}^n is a subset of \mathbb{R}^n \times \mathbb{R}^n. We use the notation F(x) to mean the set F(x) = \{ y: (x, y) \in F \}. You can think of F as an operator that maps vectors x \in \mathbb{R}^n to sets F(x) \subseteq \mathbb{R}^n. (Along this line of thinking, functions are a special kind of relation where every vector is mapped to a set consisting of exactly one element.)

The inverse relation is defined as F^{-1} = \{ (y, x): (x, y) \in F \}.

For a relation R and some parameter \lambda \in \mathbb{R}, the resolvent of R is defined as the relation

S = (I + \lambda R)^{-1}.

In other words,

\begin{aligned} S &= \{ (y, x): (x, y) \in I + \lambda R \}, \\ S &= \{ (x + \lambda y, x): (x, y) \in R \}. \end{aligned}

Connection with the proximal operator

Let f: \mathbb{R}^n \mapsto \mathbb{R} be some convex function. Recall that the proximal operator of f is defined by

\begin{aligned} \textbf{prox}_f (x) = \underset{u \in \mathbb{R}^n}{\text{argmin}} \left\{ \frac{1}{2} \| x - u \|_2^2 + f(u) \right\}. \end{aligned}

It turns out that the resolvent of the subdifferential operator is the proximal operator. Here is the proof: Let z = (I + \lambda \partial f)^{-1}(x) for some \lambda > 0. By definition of the resolvent,

\begin{aligned} z = (I + \lambda \partial f)^{-1}(x) \quad &\Leftrightarrow \quad x \in z + \lambda \partial f(z) \\ &\Leftrightarrow \quad 0 \in \lambda \partial f(z) + (z - x) \\ &\Leftrightarrow \quad 0 \in \partial \left[ \lambda f(z) + \frac{1}{2} \| z - x \|_2^2 \right] \\ &\Leftrightarrow \quad z = \underset{u}{\text{argmin}} \; \lambda f(u) + \frac{1}{2} \| u - x \|_2^2 \\ &\Leftrightarrow \quad z = \textbf{prox}_{\lambda f} (x). \end{aligned}

(Note: Setting \lambda = 1, the chain of reasoning above gives z = \textbf{prox}_{f} (x) \; \Leftrightarrow x - z \in \partial f(z), which is useful to know.)


  1. Pilanci, M. (2022). “Monotone Operators.”

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s