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.)

References:

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

Statistical Odds & Ends

Relations, resolvents and the proximal operator

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply