Proof of Properties of the Proximal Map of a Convex Function

We use the notation of the statement. Algebraic manipulations of dot products use Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$, and $\lVert v\rVert^{2}=v\cdot v$ is claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$. For $x\in\mathbb{R}^{n}$ let $\phi_{x}(z)=f(z)+\tfrac{1}{2}\lVert x-z\rVert^{2}$ as in Existence and Uniqueness of the Proximal Minimiser of a Convex Function and The Proximal Map of a Convex Function on $\mathbb{R}^n$ §proximal-map, so that $J(x)$ is the unique point at which $\phi_{x}$ attains its least value.

Throughout we use the identity, valid for all $x,y,z\in\mathbb{R}^{n}$ and $\theta\in\mathbb{R}$ and obtained by expanding with Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$,

Claim 1. Suppose first that $J(x)=y$, and let $z\in\mathbb{R}^{n}$. For $\theta\in\mathbb{R}$ with $0<\theta\le1$ put $y_{\theta}=y+\theta(z-y)=\theta z+(1-\theta)y$. Convexity of $f$ gives $f(y_{\theta})\le\theta f(z)+(1-\theta)f(y)$, and (E) gives $\tfrac{1}{2}\lVert x-y_{\theta}\rVert^{2}=\tfrac{1}{2}\lVert x-y\rVert^{2}-\theta(x-y)\cdot(z-y)+\tfrac{1}{2}\theta^{2}\lVert z-y\rVert^{2}$. Adding, and using $\phi_{x}(y)\le\phi_{x}(y_{\theta})$,

Subtracting $\phi_{x}(y)$ and dividing by the positive number $\theta$,

Since this holds for all such $\theta$, we get $(x-y)\cdot(z-y)\le f(z)-f(y)$, that is $f(z)\ge f(y)+(x-y)\cdot(z-y)$. As $z$ was arbitrary, $x-y\in\partial f(y)$ by Subdifferential of a Real-Valued Function on a Convex Subset of $\mathbb{R}^n$ §subdifferential.

Conversely suppose $x-y\in\partial f(y)$ and let $z\in\mathbb{R}^{n}$. Taking $\theta=1$ in (E) gives

while $f(z)-f(y)\ge(x-y)\cdot(z-y)$. Adding these,

so $y$ attains the least value of $\phi_{x}$, and $J(x)=y$ by the uniqueness in Existence and Uniqueness of the Proximal Minimiser of a Convex Function §minimiser.

Claim 2. Let $y\in\mathbb{R}^{n}$ and $q\in\partial f(y)$, and put $x=y+q$. Then $x-y=q\in\partial f(y)$, so $J(x)=y$ by claim 1. Since $\mathbb{R}^{n}$ is open and convex, The Subdifferential of a Convex Function on an Open Convex Set is Nonempty §nonempty shows that $\partial f(y)$ is nonempty for every $y$, so every $y\in\mathbb{R}^{n}$ is a value of $J$.

Claim 3. Put $y=J(x)$ and $y'=J(x')$. By claim 1, $x-y\in\partial f(y)$ and $x'-y'\in\partial f(y')$, so claim 1 of Elementary Calculus of the Subdifferential of a Convex Function, applied with $U=\mathbb{R}^{n}$, gives

which is the asserted inequality.

Claim 4. With $y=J(x)$ and $y'=J(x')$, claim 3 and Cauchy-Schwarz Inequality for the Euclidean Dot Product give

If $y=y'$ the asserted inequality is clear; otherwise $\lVert y-y'\rVert>0$ by claim 3 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ and we may divide by it. Thus $J$ is Lipschitz with constant $1$.

Claim 5. Let $h\in\mathbb{R}^{n}$. If $h=0$ then $Ah=0$ by claim 3 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum and both sides vanish, so assume $h\neq0$. Let $\varepsilon\in\mathbb{R}$ with $0<\varepsilon\le1$. By Differentiability at a Point for Maps Between Euclidean Spaces there is $\delta>0$ such that $\lVert J(x+k)-J(x)-Ak\rVert\le\varepsilon\lVert k\rVert$ whenever $0<\lVert k\rVert<\delta$. Choose $t\in\mathbb{R}$ with $0<t$ and $t\lVert h\rVert<\delta$, and put $D=J(x+th)-J(x)$; then, since $A(th)=t\,Ah$ by claim 3 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum and $\lVert th\rVert=t\lVert h\rVert$ by claim 5 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, we have $\lVert D-tAh\rVert\le\varepsilon t\lVert h\rVert$; so, writing $D_{t}=(1/t)D$ and using claim 5 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ again,

Applying claim 3 with $x'=x+th$ and using $J(x)-J(x')=-D$ and $x-x'=-th$ gives $\lVert D\rVert^{2}\le t\,(D\cdot h)$, and dividing by the positive number $t^{2}$,

By claim 4, $\lVert D\rVert\le t\lVert h\rVert$, so $\lVert D_{t}\rVert\le\lVert h\rVert$. From (A) and claim 6 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, $\lVert Ah\rVert\le\lVert D_{t}\rVert+\varepsilon\lVert h\rVert$, and both sides being nonnegative,

Also $(D_{t}-Ah)\cdot h\le\lVert D_{t}-Ah\rVert\lVert h\rVert\le\varepsilon\lVert h\rVert^{2}$ by Cauchy-Schwarz Inequality for the Euclidean Dot Product and (A), so $D_{t}\cdot h\le(Ah)\cdot h+\varepsilon\lVert h\rVert^{2}$. Combining with (B),

using $\varepsilon\le1$. As $\varepsilon$ was an arbitrary number with $0<\varepsilon\le1$, we conclude $\lVert Ah\rVert^{2}\le(Ah)\cdot h$.

Now suppose there is no unit vector $\nu$ with $\nu\cdot(Ah)=0$ for every $h$, and suppose $Ah_{0}=0$ for some $h_{0}\neq0$. Let $h\in\mathbb{R}^{n}$ and $s\in\mathbb{R}$. By claim 3 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, $A(h+sh_{0})=Ah+s\,Ah_{0}=Ah$, so the inequality just proved, applied to $h+sh_{0}$, gives

If $(Ah)\cdot h_{0}$ were nonzero, choosing $s$ of the opposite sign and of large absolute value would make the right-hand side smaller than the nonnegative number $\lVert Ah\rVert^{2}$, which is impossible; hence $(Ah)\cdot h_{0}=0$. Since $h$ was arbitrary, the unit vector $\nu=h_{0}/\lVert h_{0}\rVert$, whose norm is $1$ by claim 5 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, satisfies $\nu\cdot(Ah)=0$ for every $h$ by claims 1 and 4 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$, contrary to hypothesis. Therefore $Ah=0$ only for $h=0$, and if $Ah=Ah'$ then $A(h-h')=0$ by claim 3 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum and so $h=h'$; that is, $h\mapsto Ah$ is injective.