Proximal Operator

Proximal Operator

Advanced (graduate level)

1. Introduction

In modern optimization the objective is often written as a sum of a smooth term and a nonsmooth term. The $\ell_1$ regularizer of Lasso regression, image restoration by total variation (TV), an indicator function encoding a constraint — each of them contains a term that cannot be differentiated. The tool that processes such a nonsmooth function "one step at a time," much like a gradient does, is the proximal operator (prox).

The proximal operator unifies a handful of seemingly separate operations — the gradient step, projection onto a set, soft thresholding — under a single definition. This article starts from the definition and uniqueness, then treats the geometric meaning, the relationship with projection and with the resolvent (implicit gradient step), the basic properties, the standard closed forms, and finally the Moreau envelope. It closes with a bridge to the proximal gradient methods (ISTA / FISTA) that use this operator as a component (the algorithms themselves are left to a separate article).

2. Definition and Uniqueness

Proximal Operator

For a proper closed convex function $g:\mathbb{R}^n \to \mathbb{R}\cup\{+\infty\}$ and a parameter $\lambda > 0$, the proximal operator is defined by

$$\operatorname{prox}_{\lambda g}(v) \;=\; \arg\min_{x\in\mathbb{R}^n}\left\{\, g(x) + \frac{1}{2\lambda}\lVert x - v\rVert^2 \,\right\}$$

We call $v$ the input point and $\lambda$ the step size (scale).

On the right-hand side, the first term $g(x)$ expresses the wish "to make $g$ small," while the second term $\frac{1}{2\lambda}\lVert x-v\rVert^2$ expresses the wish "not to move far from the input point $v$." The proximal operator returns the compromise between these two demands, balanced by $\lambda$.

Uniqueness of the Minimizer

If $g$ is a proper closed convex function, the minimization problem above has a unique solution. That is, $\operatorname{prox}_{\lambda g}$ is a single-valued map defined on all of $\mathbb{R}^n$.

Sketch of proof

Consider the objective $h(x) = g(x) + \frac{1}{2\lambda}\lVert x-v\rVert^2$. The quadratic term $\frac{1}{2\lambda}\lVert x-v\rVert^2$ is strongly convex with modulus $\frac{1}{\lambda}$, and since $g$ is convex, $h$ is $\frac{1}{\lambda}$-strongly convex. Moreover, $g$ is bounded below by an affine function (a property of proper closed convex functions), so $h$ is coercive and closed and therefore attains its minimum. A strongly convex function has at most one minimizer, hence the solution exists and is unique. $\blacksquare$

When $g$ is nonconvex, a minimizer still exists for sufficiently small $\lambda$ but need not be unique, so prox may become set-valued. Unless stated otherwise, we take $g$ to be a proper closed convex function throughout.

3. Geometric Interpretation

Varying the step size $\lambda$ changes which of the two demands takes priority.

  • $\lambda \to 0^+$: the second term dominates and $\operatorname{prox}_{\lambda g}(v) \to v$. Almost no movement.
  • $\lambda \to \infty$: the first term dominates and $\operatorname{prox}_{\lambda g}(v)$ approaches a minimizer of $g$.

In other words, the proximal operator interpolates between the input $v$ and a minimizer of $g$, with $\lambda$ setting the "strength of the pull." Figure 1 visualizes this pull for the one-variable model case $g(x)=|x|$. Taking the input $v$ on the horizontal axis and the output $\operatorname{prox}_{\lambda g}(v)$ on the vertical axis, the whole neighborhood $[-\lambda,\lambda]$ of the origin collapses to $0$ (soft thresholding).

Figure 1: Input-to-output map (case $g=|x|$)

v prox(v) O y = v λ −λ dead zone [−λ, λ] → 0
$S_\lambda(v)$

The dashed line is the identity map $y=v$ ("do not move"). The solid soft-thresholding curve crushes $|v|\le\lambda$ to $0$ and, elsewhere, keeps slope $1$ while pulling back toward the origin by $\lambda$. This is the result of the proximal operator choosing a point that is "close to $v$ and makes $g$ small."

In the figure, $S_\lambda(v)$ is the soft-thresholding function, another name for the proximal operator of $g=\lVert\cdot\rVert_1$. Coordinatewise it is defined by

$$S_\lambda(v) = \operatorname{sign}(v)\,\max\bigl(|v|-\lambda,\;0\bigr) = \begin{cases} v-\lambda & (v > \lambda) \\ 0 & (|v| \le \lambda) \\ v+\lambda & (v < -\lambda) \end{cases}$$

The subscript $\lambda$ is the parameter for the threshold magnitude, so $S_\lambda$ means "the soft-thresholding function with threshold $\lambda$." The dead zone of width $\lambda$ crushes small components to $0$ (sparsification), while the surviving components shrink toward the origin by $\lambda$. The derivation is given in §7.

4. Projection as a Special Case

The most important special case of the proximal operator is the orthogonal projection. For a convex set $C$, define the indicator function by

$$\iota_C(x) = \begin{cases} 0 & (x \in C) \\ +\infty & (x \notin C) \end{cases}$$

Then $\iota_C$ is a proper closed convex function, and its proximal operator is

$$\operatorname{prox}_{\lambda \iota_C}(v) = \arg\min_{x\in C}\; \frac{1}{2\lambda}\lVert x-v\rVert^2 = \arg\min_{x\in C}\; \lVert x-v\rVert^2 = \Pi_C(v)$$

that is, exactly the orthogonal projection $\Pi_C$ onto $C$ (independent of $\lambda$). The indicator function imposes an infinite penalty for leaving $C$, so prox returns the point of $C$ closest to $v$ — the projection.

Figure 2: The proximal operator of an indicator function is a projection

$C$
$v$
$\Pi_C(v)$
From a point $v$ outside the set $C$, the nearest point is the projection $\Pi_C(v)$. The proximal operator can be understood as extending this "pull back onto a constraint set" into a "soft pull back" by a general convex function $g$.

5. Resolvent and Implicit Gradient Step

The proximal operator can be characterized algebraically through the subdifferential $\partial g$. Since $x = \operatorname{prox}_{\lambda g}(v)$ is a minimizer of the objective $g(x)+\frac{1}{2\lambda}\lVert x-v\rVert^2$, the optimality condition (that $0$ belongs to the subdifferential) gives

$$0 \in \partial g(x) + \frac{1}{\lambda}(x - v) \quad\Longleftrightarrow\quad v \in x + \lambda\,\partial g(x) = (I + \lambda\partial g)(x).$$

Solving for $x$,

$$x = (I + \lambda\partial g)^{-1}(v),$$

so the proximal operator equals the resolvent $(I+\lambda\partial g)^{-1}$ of the subdifferential operator $\partial g$. The key point is that although $\partial g$ is in general set-valued (multivalued), its resolvent is single-valued (the uniqueness of the previous section).

Why "backward (implicit) gradient step"?

If $g$ is smooth, then $\partial g = \{\nabla g\}$, so the relation above reads $x = v - \lambda\nabla g(x)$. Note that the gradient on the right is evaluated at the updated point $x$. Whereas the ordinary (forward, explicit) gradient step $x = v - \lambda\nabla g(v)$ takes the gradient at the current point $v$, the proximal operator corresponds to an implicit (backward) Euler step that takes the gradient at the updated point. Being implicit, it is stable even for large $\lambda$ and remains well defined through the subdifferential even when $g$ is nonsmooth.

6. Basic Properties

Fixed points are minimizers of $g$

A point $x^\star$ being a fixed point of $\operatorname{prox}_{\lambda g}$, i.e. $x^\star = \operatorname{prox}_{\lambda g}(x^\star)$, is equivalent to $x^\star$ being a minimizer of $g$.

Proof

The resolvent form $x^\star = (I+\lambda\partial g)^{-1}(x^\star)$ is equivalent to $x^\star \in x^\star + \lambda\partial g(x^\star)$, i.e. $0 \in \partial g(x^\star)$. This is precisely the condition for $x^\star$ to be a (global) minimizer of $g$. $\blacksquare$

This fact underlies why the proximal iteration $x_{k+1}=\operatorname{prox}_{\lambda g}(x_k)$ (the proximal point method) converges to a minimizer of $g$.

Firm nonexpansiveness

For all $x, y$,

$$\lVert \operatorname{prox}_{\lambda g}(x) - \operatorname{prox}_{\lambda g}(y)\rVert^2 \;\le\; \bigl\langle \operatorname{prox}_{\lambda g}(x) - \operatorname{prox}_{\lambda g}(y),\; x - y \bigr\rangle.$$

In particular, by Cauchy–Schwarz, $\lVert \operatorname{prox}_{\lambda g}(x) - \operatorname{prox}_{\lambda g}(y)\rVert \le \lVert x-y\rVert$, i.e. the proximal operator is nonexpansive (1-Lipschitz).

Sketch of proof

Set $u=\operatorname{prox}_{\lambda g}(x)$ and $w=\operatorname{prox}_{\lambda g}(y)$. The optimality conditions give $\frac{1}{\lambda}(x-u)\in\partial g(u)$ and $\frac{1}{\lambda}(y-w)\in\partial g(w)$. Substituting into the monotonicity of the subdifferential $\langle s_u - s_w,\, u-w\rangle \ge 0$ ($s_u\in\partial g(u), s_w\in\partial g(w)$) yields $\bigl\langle (x-u)-(y-w),\, u-w\bigr\rangle \ge 0$. Expanding and rearranging gives $\lVert u-w\rVert^2 \le \langle u-w,\, x-y\rangle$. $\blacksquare$

Separable means coordinatewise

When $g$ separates across coordinates, $g(x)=\sum_{i} g_i(x_i)$, the proximal operator also acts coordinatewise:

$$\bigl(\operatorname{prox}_{\lambda g}(v)\bigr)_i = \operatorname{prox}_{\lambda g_i}(v_i).$$

The soft thresholding of the $\ell_1$ norm can be written coordinatewise precisely because of this property.

Translation and scaling rules

  • Translation $g(x)=h(x-a)$: $\operatorname{prox}_{\lambda g}(v) = a + \operatorname{prox}_{\lambda h}(v-a)$
  • Scaling $g(x)=h(x/\rho)$ ($\rho\neq 0$): $\operatorname{prox}_{\lambda g}(v) = \rho\,\operatorname{prox}_{\lambda h/\rho^2}(v/\rho)$
  • Linear term $g(x)=h(x)+\langle b, x\rangle$: $\operatorname{prox}_{\lambda g}(v) = \operatorname{prox}_{\lambda h}(v-\lambda b)$
  • Quadratic term $g(x)=h(x)+\tfrac{\mu}{2}\lVert x\rVert^2$: $\operatorname{prox}_{\lambda g}(v) = \operatorname{prox}_{\tilde\lambda h}\!\bigl(\tfrac{v}{1+\lambda\mu}\bigr)$, with $\tilde\lambda=\tfrac{\lambda}{1+\lambda\mu}$

Combining these rules, the proximal operator of a complicated $g$ can often be reduced to a known closed form.

7. Table of Closed Forms

The proximal operator is practical because, for the standard regularizers, it can be computed in closed form. The main cases follow.

Function $g(x)$$\operatorname{prox}_{\lambda g}(v)$Remark
$0$$v$Identity map
Constant $c$$v$Constants are irrelevant to the solution
$\iota_C(x)$ (indicator)$\Pi_C(v)$Projection onto the set $C$
$\tfrac{1}{2}\lVert x\rVert^2$$\dfrac{v}{1+\lambda}$Uniform shrinkage
$\lVert x\rVert_1$$S_\lambda(v)$ (soft thresholding)Coordinatewise; zeroing yields sparsity
$\lVert x\rVert_2$$\left(1-\dfrac{\lambda}{\lVert v\rVert_2}\right)_{\!+} v$Block soft thresholding
$\lVert x\rVert_\infty$$v - \Pi_{\lambda B_1}(v)$Computed via projection onto the $\ell_1$ ball (Moreau decomposition)
Box constraint $\iota_{[l,u]}(x)$$\operatorname{clip}(v,\,l,\,u)$Coordinatewise clipping to $[l,u]$

Derivation of soft thresholding ($g=\lVert\cdot\rVert_1$)

Since the $\ell_1$ norm separates coordinatewise, it suffices to solve the one-variable problem

$$\min_{x}\; |x| + \frac{1}{2\lambda}(x-v)^2$$

The optimality condition for $x \neq 0$ is $\operatorname{sign}(x) + \frac{1}{\lambda}(x-v) = 0$, i.e. $x = v - \lambda\,\operatorname{sign}(x)$. Splitting into cases,

$$\operatorname{prox}_{\lambda|\cdot|}(v) = S_\lambda(v) = \operatorname{sign}(v)\,\max\bigl(|v|-\lambda,\;0\bigr) = \begin{cases} v-\lambda & (v > \lambda) \\ 0 & (|v| \le \lambda) \\ v+\lambda & (v < -\lambda) \end{cases}$$

For $|v|\le\lambda$, $x=0$ is optimal (the subdifferential $[-1,1]$ of $|\cdot|$ at $0$ satisfies the condition $\frac{1}{\lambda}(0-v)\in[-1,1]$). This action of "crushing small components to $0$" is exactly the mechanism by which the Lasso makes solutions sparse. The solid curve in Figure 1 depicts this map.

Moreau decomposition

The proximal operator satisfies a beautiful identity linking a function to its dual. Writing $g^*$ for the convex conjugate of $g$, for every $v$,

$$v = \operatorname{prox}_{\lambda g}(v) + \lambda\,\operatorname{prox}_{g^*/\lambda}\!\bigl(v/\lambda\bigr).$$

This is the Moreau decomposition. Taking $g=\iota_C$ (so $g^*$ is the support function) recovers the orthogonal decomposition of projections, "point $=$ projection onto the set $+$ projection onto the polar set." The reason the prox of $\lVert\cdot\rVert_\infty$ in the table above can be computed via projection onto the $\ell_1$ ball is likewise this decomposition, together with the fact that $\lVert\cdot\rVert_\infty$ is the conjugate of the $\ell_1$ norm. For the convex conjugate, see the Legendre transform.

8. The Moreau Envelope

Instead of the value of the proximal operator, focusing on the minimum value of its minimization problem yields a smoothed version of $g$.

Moreau Envelope

For a proper closed convex function $g$ and a parameter $\lambda>0$, the Moreau envelope is defined by

$$M_{\lambda g}(v) = \min_{x}\left\{\, g(x) + \frac{1}{2\lambda}\lVert x-v\rVert^2 \,\right\}$$

The $x$ that attains the minimum is precisely $\operatorname{prox}_{\lambda g}(v)$.

Main properties

  • $M_{\lambda g}$ is continuously differentiable even when $g$ is nonsmooth, with gradient $$\nabla M_{\lambda g}(v) = \frac{1}{\lambda}\bigl(v - \operatorname{prox}_{\lambda g}(v)\bigr).$$
  • This gradient is $\frac{1}{\lambda}$-Lipschitz, i.e. $M_{\lambda g}$ is $\frac{1}{\lambda}$-smooth.
  • It approximates $g$ from below: $M_{\lambda g}(v) \le g(v)$, and $M_{\lambda g}(v)\to g(v)$ as $\lambda\to 0^+$.
  • It preserves the minimum value and the minimizers: $\min_v M_{\lambda g}(v) = \min_x g(x)$, and the $\arg\min$ coincide.

Figure 3: The Moreau envelope rounds the corner

x O
$g(x)=|x|$
$M_{\lambda g}(x)$
$-\lambda$
$\lambda$
The Moreau envelope of $g(x)=|x|$ is the Huber function — a parabola $\frac{x^2}{2\lambda}$ near the origin and $|x|-\frac{\lambda}{2}$ for $|x|>\lambda$. The sharp corner is replaced by a smooth valley, while the minimum value and the minimizer (both at the origin) are preserved. Smaller $\lambda$ makes it closer to the original V shape.

Relationship between the proximal operator and the envelope

Rearranging the gradient identity $\nabla M_{\lambda g}(v)=\frac{1}{\lambda}(v-\operatorname{prox}_{\lambda g}(v))$ gives $\operatorname{prox}_{\lambda g}(v) = v - \lambda\nabla M_{\lambda g}(v)$. In other words, a "proximal step on $g$" equals a "gradient step on the smooth $M_{\lambda g}$." Bridging nonsmooth minimization to smooth minimization is the role of the Moreau envelope, and it is also the theoretical foundation of the proximal gradient methods of the next section.

9. Bridge to Proximal Gradient Methods

The main arena of the proximal operator is composite minimization

$$\min_x\; F(x) = f(x) + g(x)$$

where $f$ is an $L$-smooth convex function (e.g. squared error) and $g$ is nonsmooth convex (e.g. the $\ell_1$ norm, an indicator function). Because of $g$ one cannot apply the gradient method directly, but alternating a gradient step on $f$ with a proximal step on $g$ lets one make progress:

$$x_{k+1} = \operatorname{prox}_{\lambda g}\!\bigl(x_k - \lambda\nabla f(x_k)\bigr).$$

This is the proximal gradient method (ISTA), and its accelerated version with extrapolation is FISTA. Since the subject of this article is the proximal operator that carries out one step of each iteration, the construction of the algorithm, its convergence rate (ISTA is $O(1/k)$, FISTA is $O(1/k^2)$), and implementation refinements (backtracking, restart) are left to the next article.

Further reading

10. Frequently Asked Questions

Q1. What is the proximal operator?

It is the map $\operatorname{prox}_{\lambda g}(v)=\arg\min_x\{g(x)+\frac{1}{2\lambda}\lVert x-v\rVert^2\}$ defined for a convex function $g$ and a parameter $\lambda>0$. It returns a compromise point that stays near the input $v$ while making $g$ small. Because the objective is strongly convex, the minimizer is unique, so prox is single-valued on the whole space. It is a generalization of the gradient step to nonsmooth functions and can also be read as a backward (implicit) gradient step.

Q2. How is the proximal operator related to projection?

The proximal operator of the indicator function $\iota_C$ of a convex set $C$ coincides with the orthogonal projection $\Pi_C$ onto $C$ (independent of $\lambda$). Hence projection is a special case of the proximal operator, and prox can be seen as extending "projection onto a constraint set" to a general convex function.

Q3. Why is the proximal operator of the $\ell_1$ norm the soft-thresholding function?

Since $\lVert x\rVert_1$ separates coordinatewise, it suffices to minimize $|x|+\frac{1}{2\lambda}(x-v)^2$ in each coordinate. Solving the optimality condition $0\in\operatorname{sign}(x)+\frac{1}{\lambda}(x-v)$ gives $x=0$ for $|v|\le\lambda$, $x=v-\lambda$ for $v>\lambda$, and $x=v+\lambda$ for $v<-\lambda$. In closed form this is the soft thresholding $S_\lambda(v)=\operatorname{sign}(v)\max(|v|-\lambda,0)$, whose dead zone of width $\lambda$ crushes small components to $0$. This is the source of the sparsity of the Lasso.

Q4. How is the proximal operator related to proximal gradient methods?

For a composite minimization $\min f(x)+g(x)$ ($f$ smooth, $g$ nonsmooth), the iteration that alternates a gradient step on $f$ with a proximal step on $g$, $x_{k+1}=\operatorname{prox}_{\lambda g}(x_k-\lambda\nabla f(x_k))$, is the proximal gradient method (ISTA). The proximal operator is the building block of one iteration; when the prox of $g$ has a closed form, one iteration costs about the same as an ordinary gradient step. The details of the algorithm (forward-backward splitting, convergence, applications) are covered in Proximal Gradient Method and FISTA.

11. References

  • Parikh, N., & Boyd, S. (2014). Proximal Algorithms. Foundations and Trends in Optimization, 1(3), 127–239. Online
  • Beck, A. (2017). First-Order Methods in Optimization. SIAM.
  • Bauschke, H. H., & Combettes, P. L. (2017). Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed. Springer.
  • Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press.
  • Beck, A., & Teboulle, M. (2009). A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems. SIAM J. Imaging Sciences, 2(1), 183–202.
  • Wikipedia: Proximal operator
  • Wikipedia: Moreau envelope