Firm Non Expansiveness in the Context of Proximal Mapping / Proximal Operators $\newcommand{\prox}{\operatorname{prox}}$
Probably the most remarkable property of the proximal operator is the fixed point property:
The point $x^*$ minimizes $f$ if and only if $x^* = \prox_f(x^*) $
So, indeed, $f$ can be minimized by find a fixed point of its proximal operator. 
See Proximal Algorithms by Neal Parikh and Stephen Boyd.
Question 1. In the paper given above, author is saying:
If $\prox_f$ were a contraction, i.e., Lipschitz continuous with
constant less than $1$, repeatedly applying $\prox_f$ would find a (here,
unique) fixed point
Why the bound on the first-order derivative guarantees finding a fixed point by repeatedly applying proximal operator?
Question 2. Let me quote a paragraph from the same paper:
It turns out that while $\prox_f$ need not be a contraction (unless $f$ is strongly convex), it does have a different property, firm nonexpansiveness, sufficient for fixed point iteration:
$\|\prox_f(x) - \prox_f(y)\|^2_2 \le (x-y)^T (\prox_f(x) - \prox_f(y))$
$\forall x,y \in \mathbb{R}^n$
Firmly nonexpansive operators are special cases of nonexpansive operators (those that are Lipschitz continuous with constant 1). Iteration of a general nonexpansive operator need not converge to a fixed point: consider operators like $-I$ or rotations. However, it tunrs out that if $N$ is nonexpansive, then the operator $T = (1-\alpha)I + \alpha N$, where $\alpha \in (0,1)$ has the same fixed points as $N$ and simple iteration of $T$ will converge to a fixed point of $T$ (and thus of $N$), i.e. the sequence:
$x^{k+1} := (1-\alpha)x^k +\alpha N(x^k)$
will converge to a fixed point of $N$. Put differently, damped iteration of
a nonexpansive operator will converge to one of its fixed points.
Operators in the form $(1-\alpha)I + \alpha N$, where $N$ is non-expansive and $\alpha \in (0,1)$, are called $\alpha$-averaged operators.
Firmly nonexpansive operators are averaged: indeed, they are precisely the (1/2)-averaged
operators.
Why "unless $f$ is strongly convex"?
What is the intuition behind the given expression for firm nonexpansiveness?
How can you show that firm nonexpansive operators are $\alpha$-averaged with $\alpha = \frac{1}{2}$?
Is anyone aware of the proof of why proximal map is firm nonexpansive?
 A: For the first one it is enough to assume it is lipshitz continous with constant $1$ since $prox_f$ is by definition a self-mapping to the domain of $f$. Thats the first condition needed for the Banach-Fixpoint-Theorem. Now it also is contractive since its lipshitz continuous with constant less than 1 so we can use the Theorem to get a fixpoint iterativly.
A: Here's a short proof that proximal operators are firmly nonexpansive.  Let $f:\mathbb R^n \to \mathbb R \cup \{\infty\}$ be closed convex proper (CCP).  Assume that
\begin{equation}
u_1 = \operatorname{prox}_f(x_1) \quad \text{and} \quad u_2 = \operatorname{prox}_f(x_2).
\end{equation}
Equivalently,
\begin{equation}
\tag{$\spadesuit$} x_1 - u_1 \in \partial f(u_1) \quad \text{and} \quad x_2 - u_2 \in \partial f(u_2).
\end{equation}
Now we use the (fundamentally important) fact that $\partial f$ is a monotone mapping, which tells us that
\begin{align}
&\langle x_1 - u_1 - (x_2 - u_2), u_1 - u_2 \rangle \geq 0 \\
\tag{$\heartsuit$}\implies & \langle x_1 - x_2, u_1 - u_2 \rangle \geq \| u_1 - u_2 \|_2^2.
\end{align}
This shows that $\operatorname{prox}_f$ is firmly nonexpansive.
Comments:


*

*When working with prox-operators, often the very first step is to express $u = \operatorname{prox}_f(x)$ in the equivalent form $x - u \in \partial f(u)$.  This is a statement you can work with, involving more primitive notions.

*The fact that $\partial f$ is monotone is so fundamental, that it is extremely tempting to invoke monotonicity once we have written down equation $(\spadesuit)$.  In fact, much of the theory of prox-operators can be generalized to the setting of "monotone operators" which are set-valued mappings (such as $\partial f$) which satisfy the monotonicity property.  From this viewpoint, the most important fact about $\partial f$ is that it is monotone.

*The fact that this derivation is so short, essentially only two lines, helps to explain how the "firmly nonexpansive" property might be discovered in the first place.  A mathematician playing around with these definitions might stumble across the inequality $(\heartsuit)$ rather quickly.  A mathematician would notice that inequality $(\heartsuit)$ implies that $\operatorname{prox}_f$ is nonexpansive (because $\langle x_1 - x_2, u_1 - u_2 \rangle \leq \|x_1 - x_2\|_1 \| u_1 - u_2 \|_2$), but it may seem wasteful to replace the inequality $(\heartsuit)$ with the inequality $\|u_1 - u_2 \|_2 \leq \|x_1 - x_2 \|_2$, because this latter inequality is less tight.  

A: You can proof the non-expansiveness of the proximal operator as following:
$\DeclareMathOperator{\prox}{prox}$
Note that the proof is similar to the proof of the (firm) non-expansiveness of the projection operator [1].
You can imagine the the proximal operator as some kind of generalised projection operator.
Proof:
We pick two arbitrary points $z_1$, $z_2$.
\begin{align}
    (z_1 - \prox_f(z_1))^\top (x- \prox_f(z_1)) &\le 0 \quad \forall x \in \mathcal C \\
\end{align}
By definition of the proximal operator $\prox_f(z_2)$ is in $\mathcal C$.
The optimality condition for $\prox_f(z_1)$ is:
\begin{align}
    (f_{\prox_f(z_1)} + \prox_f(z_1) - z_1)^\top (\prox_f (z_2) - \prox_f (z_1)) &\ge 0 \label{eq:opt_cond_1}\\
\end{align}
and for $\prox_f(z_2)$:
\begin{align}
    (f_{\prox_f(z_2)} + \prox_f(z_2) - z_2)^\top (\prox_f (z_1) - \prox_f (z_2)) &\ge 0 \\
    (z_2 - f_{\prox_f(z_2)} - \prox_f(z_2) - )^\top (\prox_f (z_2) - \prox_f (z_1)) &\ge 0 \label{eq:opt_cond_2} 
\end{align}
The subgradient properties for $f_{\prox_f(z_1)}$ and $f_{\prox_f (z_2)}$ are:
\begin{align}
    f(\prox_f(z_2)) - f(\prox_f(z_1)) \ge f_{\prox_f(z_2)}^\top (\prox_f(z_2) - \prox_f(z_1)) \label{eq:subgrad_1}\\
    f(\prox_f(z_1)) - f(\prox_f(z_2)) \ge f_{\prox_f(z_1)}^\top (\prox_f(z_1) - \prox_f(z_2)) \label{eq:subgrad_2}\\
\end{align}
Adding the two subgradient properties results to:
\begin{align}
    0 \ge (f_{\prox_f(z_2)} - f_{\prox_f(z_1)})^\top (\prox_f(z_2) - \prox_f(z_1)) \label{eq:subgrad_zero}
\end{align}
Adding the two optimality conditions leads us to:
\begin{align}
    ((z_2 - z_1) + (f_{\prox_f(z_1)} - f_{\prox_f(z_2)}) + (\prox_f(z_1) - \prox_f(z_2)))^\top (\prox_f(z_2) - \prox_f(z_1)) &\ge 0 \\
    (- (z_2 - z_1) + (f_{\prox_f(z_2)} - f_{\prox_f(z_1)}) + (\prox_f(z_2) - \prox_f(z_1)))^\top  (\prox_f(z_2) - \prox_f(z_1)) &\le 0
\end{align}
We use that the subgradient properties to bound the subgradients by zero:
\begin{align}
        (\prox_f(z_2) - \prox_f(z_1))^\top (\prox_f(z_2) - \prox_f(z_1)) &\le ((z_2 - z_1) - (f_{\prox_f(z_2)} - f_{\prox_f(z_1)}))^\top (\prox_f(z_2) - \prox_f(z_1)) \\
         (\prox_f(z_2) - \prox_f(z_1))^\top (\prox_f(z_2) - \prox_f(z_1)) &\le (z_2 - z_1)^\top  (\prox_f(z_2) - \prox_f(z_1))
\end{align}
And use Cauchy-Schwarz:
\begin{align}
    ||\prox_f(z_2) - \prox_f(z_1)||^2 &\le ||z_2 - z_1|| ||\prox_f(z_2) - \prox_f(z_1)|| \\
     ||\prox_f(z_2) - \prox_f(z_1)|| &\le ||z_2 - z_1|| \\ 
&&\square 
\end{align}
A: I can explain the first question, the author said "if $prox_f$ were a contraction", which is not guaranteed. Banach fixed-point theorem tells us repeatedly applying contraction would find a (here, unique) fixed point. So if $prox_f$ is a contraction, then by repeatedly applying proximal operator will result a fixed point.
