The proximal map is an implicit first-order step: instead of linearizing a nonsmooth function, it minimizes the function plus a quadratic penalty for moving too far. The same construction produces a smooth envelope whose gradient records the proximal displacement.
Existence, uniqueness, and optimality
Definition. For a proper, closed, convex function \(g:\mathbb R^d\to(-\infty,+\infty]\) and \(\eta>0\), \[ \operatorname{prox}_{\eta g}(x) = \operatorname*{arg\,min}_{z} \left\{g(z)+\frac1{2\eta}\|z-x\|^2\right\}. \]
Resolvent identity. The minimizer exists and is unique. A point \(z\) equals \(\operatorname{prox}_{\eta g}(x)\) if and only if \[ 0\in\partial g(z)+\frac1\eta(z-x), \] equivalently \[ x\in z+\eta\partial g(z),\qquad \operatorname{prox}_{\eta g}=(I+\eta\partial g)^{-1}. \]
Proof. The quadratic term makes the objective \(1/\eta\)-strongly convex and coercive, while closedness gives lower semicontinuity. It therefore has a unique minimizer. The convex Fermat rule and the subdifferential sum rule give the displayed inclusion, and rearranging gives the resolvent form.
Firm nonexpansiveness
Proximal contraction inequality. For \(p=\operatorname{prox}_{\eta g}(x)\) and \(q=\operatorname{prox}_{\eta g}(y)\), \[ \|p-q\|^2\le\langle p-q,x-y\rangle. \] Consequently the proximal map is \(1\)-Lipschitz.
Proof. The optimality conditions give \((x-p)/\eta\in\partial g(p)\) and \((y-q)/\eta\in\partial g(q)\). Monotonicity of the convex subdifferential yields \[ \left\langle \frac{x-p}{\eta}-\frac{y-q}{\eta},p-q \right\rangle\ge0. \] Rearrangement proves firm nonexpansiveness; Cauchy-Schwarz then gives \(\|p-q\|\le\|x-y\|\).
The smooth Moreau envelope
Definition. The Moreau envelope is \[ g_\eta(x) =\min_z\left\{g(z)+\frac1{2\eta}\|z-x\|^2\right\}. \]
Differentiability of the envelope. The function \(g_\eta\) is finite, convex, and continuously differentiable, with \[ \nabla g_\eta(x) =\frac1\eta\left(x-\operatorname{prox}_{\eta g}(x)\right). \] Its gradient is \(1/\eta\)-Lipschitz.
Proof. Let \(p(x)\) denote the unique proximal point. Evaluating the minimization defining \(g_\eta(y)\) at \(p(x)\) gives an upper directional bound, while evaluating \(g_\eta(x)\) at \(p(y)\) gives the reverse bound. After expanding the squared norms and letting \(y\to x\), firm nonexpansiveness implies \[ g_\eta(y)-g_\eta(x) =\left\langle\frac{x-p(x)}\eta,y-x\right\rangle +o(\|y-x\|). \] This proves the gradient formula. Moreover \(I-\operatorname{prox}_{\eta g}\) is firmly nonexpansive whenever the proximal map is, so \(\|\nabla g_\eta(x)-\nabla g_\eta(y)\| \le\eta^{-1}\|x-y\|\).
At a differentiability point of \(g\), the proximal equation reads \(p=x-\eta\nabla g(p)\): an implicit gradient step. The envelope replaces a possibly set-valued subgradient by the single smooth vector \(\nabla g_\eta(x)\).
Moreau decomposition
Primal-dual decomposition. For every \(x\), \[ x= \operatorname{prox}_{\eta g}(x) +\eta\operatorname{prox}_{g^*/\eta}(x/\eta). \]
Proof. Put \(p=\operatorname{prox}_{\eta g}(x)\) and \(u=(x-p)/\eta\). Proximal optimality gives \(u\in\partial g(p)\), hence \(p\in\partial g^*(u)\). Therefore \(0\in\partial(g^*/\eta)(u)+u-x/\eta\), which says \(u=\operatorname{prox}_{g^*/\eta}(x/\eta)\). Since \(x=p+\eta u\), the decomposition follows.
Projection and thresholding
Indicator functions. If \(g=\iota_C\) for a nonempty closed convex set, then \(\operatorname{prox}_{\eta g}=P_C\). The Moreau envelope is \(g_\eta(x)=\operatorname{dist}(x,C)^2/(2\eta)\).
Soft thresholding. For \(g(z)=\lambda\|z\|_1\), the problem separates by coordinate and \[ [\operatorname{prox}_{\eta g}(x)]_i =\operatorname{sign}(x_i)(|x_i|-\eta\lambda)_+. \] For the nuclear norm, the analogous operation applies soft thresholding to singular values.