Xrfgtjtk

For a convex function $h$, its proximal operator is defined as:
$$operatorname{prox}_h(x)=argmin_u Big(h(u)+frac{1}{2}|u-x|^2Big)$$
Can anyone provide an intuitive explanation/motivation of proximal mapping?

Here are two interpretations which can lend useful intuition in some circumstances:

Prox is a generalized projection

Consider the indicator of some nonempty convex set $X$: $$i_X(x) = begin{cases}0 & text{if } x in X \ infty & text{if } x not in Xend{cases}.$$ Then we find that the proximal mapping is the projection onto $X$: $$begin{align}text{prox}_{alpha i_X}(y) &= underset{x}{text{argmin}}(alpha i_X(x)+frac{1}{2}|x - y|^2) \ &= underset{x in X}{text{argmin}}(frac{1}{2}|x - y|^2) \ &= text{proj}_X(y).end{align}$$

Prox is backward Euler

Consider the backward Euler update: $x^{k+1} = x^k - alpha nabla f(x^{k+1})$ for some differentiable $f$. This update can be viewed as a proximal point update $x^{k+1} = text{prox}_{alpha f}(x^k)$, since for differentiable convex functions the optimality condition is $0 = nabla (alpha f(x^star) + frac{1}{2}|x^star - x^k|^2) = alpha nabla f(x^star) + x^star - x^k$.

If $h$ is a closed convex function, then the proximal operator of $h$ (with parameter $t > 0$) is defined by
$$
text{prox}_{th}(hat x) = arg min_x , h(x) + frac{1}{2t} |x - hat x |_2^2.
$$
When we evaluate the prox-operator of $h$, we are attempting to reduce the value of $h$, but we are penalized for straying too far from $hat x$. (The parameter $t$ is like a "step size" that controls how much we are penalized for moving away from $hat x$.)

You can see that evaluating a prox-operator might be a useful sub-step in an optimization algorithm. For example, suppose that we want to solve the optimization problem
$$
text{minimize} quad g(x) + h(x)
$$
where $g$ and $h$ are convex, $g$ is differentiable, and $h$ is "simple" in the sense that its prox-operator can be evaluated efficiently. (Importantly, $h$ is not required to be differentiable.) A natural strategy is to first reduce the value of $g$ by taking a step in the negative gradient direction, then reduce the value of $h$ by applying the prox-operator of $h$, and repeat. This strategy yields the following iteration:
$$
x^{k+1} = text{prox}_{th}(x^k - t nabla g(x^k)).
$$
(This iteration is known as the proximal gradient method. You could implement it right now in Python to solve famous optimization problems such as the Lasso problem from statistics.)

Here is an alternative way to derive the proximal gradient method and, in the process, discover the proximal operator. Suppose again that we want to minimize $g(x) + h(x)$, with $g$ and $h$ as given above. A natural strategy is to replace $g$ with a local linear approximation to $g$ (this is the fundamental strategy of calculus), and also to add a penalty term to the objective function which penalizes us from straying too far from the current iterate (this ensures that the local linear approximation to $g$ remains accurate). This strategy yields the following iteration:
$$
x^{k+1} = arg min_x quad h(x) + underbrace{g(x^k) + nabla g(x^k)^T(x - x^k)}_{approx , g(x)} + frac{1}{2t} |x - x^k |_2^2.
$$
Now if we combine the two terms on the right by completing the square, and then omit terms that do not depend on $x$, we find that
begin{align}
x^{k+1} &= arg min_x , h(x) + frac{1}{2t} |x - (x^k - tnabla g(x^k)) |_2^2 \
&= text{prox}_{th}(x^k - tnabla g(x^k)).
end{align}
This is the proximal gradient iteration. We see that the proximal operator of $h$ has appeared out of thin air. To me this seems like the most likely way that someone would discover the idea of a proximal operator.

Another motivation for the proximal operator comes from the viewpoint of monotone operator theory. Minimizing a closed convex function $h$ is equivalent to finding a point $x$ such that
$$
tag{1} 0 in partial h(x).
$$
Here $partial h(x)$ is the subdifferential of $h$ at $x$. The set-valued mapping $x mapsto partial h(x)$ is the best example of a "monotone operator", and problem (1) is called a "monotone inclusion problem". Multiplying both sides by $t$ and then adding $x$ to both sides, we find that
begin{align}
& 0 in partial h(x) \
iff & x in (I + t partial h)(x) \
iff & x in (I + t partial h)^{-1}(x).
end{align}
The operator $(I + t partial h)^{-1}$ is called the "resolvent" of the operator $partial h$, and it has nice properties such as the following: if $x in mathbb R^n$, then $(I + t partial h)^{-1}(x)$ is a singleton. Thus, $(I + t partial h)^{-1}$ can be viewed as a function (rather than a set-valued mapping), and solving $0 in partial h(x)$ is equivalent to solving

$$
x = (I + t partial h)^{-1}(x).
$$
A natural idea is to solve for $x$ using fixed point iteration. The resulting iteration is
$$
x^{k+1} = (I + t partial h)^{-1}(x^k).
$$

Punch line: The function $(I + t partial h)^{-1}$ is none other than the proximal operator of $h$, and this iteration is known as the "proximal point algorithm".