Proof of Properties of the Proximal Map of a Convex Function

We use the notation of the statement. Algebraic manipulations of dot products use The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite, and $\lVert v\rVert^{2}=v\cdot v$ is claim 1 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square. 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$ (i), 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 The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite,

$$\bigl\lVert x-\bigl(y+\theta(z-y)\bigr)\bigr\rVert^{2}=\lVert x-y\rVert^{2}-2\theta\,(x-y)\cdot(z-y)+\theta^{2}\lVert z-y\rVert^{2}. \tag{E}$$

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})$,

$$\phi_{x}(y)\le\phi_{x}(y)+\theta\bigl(f(z)-f(y)\bigr)-\theta\,(x-y)\cdot(z-y)+\tfrac{1}{2}\theta^{2}\lVert z-y\rVert^{2}.$$

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

$$(x-y)\cdot(z-y)\le f(z)-f(y)+\tfrac{1}{2}\theta\lVert z-y\rVert^{2}\qquad\text{for every }\theta\text{ with }0<\theta\le1 .$$

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$ (i).

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

$$\tfrac{1}{2}\lVert x-z\rVert^{2}=\tfrac{1}{2}\lVert x-y\rVert^{2}-(x-y)\cdot(z-y)+\tfrac{1}{2}\lVert z-y\rVert^{2},$$

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

$$\phi_{x}(z)-\phi_{x}(y)\ge\tfrac{1}{2}\lVert z-y\rVert^{2}\ge0 ,$$

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

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 (ii) 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

$$0\le\bigl((x-y)-(x'-y')\bigr)\cdot(y-y')=(x-x')\cdot(y-y')-\lVert y-y'\rVert^{2},$$

which is the asserted inequality.

Claim 4. With $y=J(x)$ and $y'=J(x')$, claim 3 and The Cauchy-Schwarz Inequality on $\mathbb{R}^n$ give

$$\lVert y-y'\rVert^{2}\le(y-y')\cdot(x-x')\le\lVert y-y'\rVert\,\lVert x-x'\rVert .$$

If $y=y'$ the asserted inequality is clear; otherwise $\lVert y-y'\rVert>0$ by claim 3 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square 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 Functions 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 Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square, we have $\lVert D-tAh\rVert\le\varepsilon t\lVert h\rVert$; so, writing $D_{t}=(1/t)D$ and using claim 5 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square again,

$$\lVert D_{t}-Ah\rVert\le\varepsilon\lVert h\rVert . \tag{A}$$

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}$,

$$\lVert D_{t}\rVert^{2}\le D_{t}\cdot h . \tag{B}$$

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 Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square, $\lVert Ah\rVert\le\lVert D_{t}\rVert+\varepsilon\lVert h\rVert$, and both sides being nonnegative,

$$\lVert Ah\rVert^{2}\le\lVert D_{t}\rVert^{2}+2\varepsilon\lVert h\rVert\,\lVert D_{t}\rVert+\varepsilon^{2}\lVert h\rVert^{2}\le\lVert D_{t}\rVert^{2}+2\varepsilon\lVert h\rVert^{2}+\varepsilon^{2}\lVert h\rVert^{2}.$$

Also $(D_{t}-Ah)\cdot h\le\lVert D_{t}-Ah\rVert\lVert h\rVert\le\varepsilon\lVert h\rVert^{2}$ by The Cauchy-Schwarz Inequality on $\mathbb{R}^n$ and (A), so $D_{t}\cdot h\le(Ah)\cdot h+\varepsilon\lVert h\rVert^{2}$. Combining with (B),

$$\lVert Ah\rVert^{2}\le(Ah)\cdot h+\bigl(3\varepsilon+\varepsilon^{2}\bigr)\lVert h\rVert^{2}\le(Ah)\cdot h+4\varepsilon\lVert h\rVert^{2},$$

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

$$\lVert Ah\rVert^{2}\le(Ah)\cdot(h+sh_{0})=(Ah)\cdot h+s\,\bigl((Ah)\cdot h_{0}\bigr).$$

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 Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square, satisfies $\nu\cdot(Ah)=0$ for every $h$ by claims 1 and 4 of The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite, 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.