Does the non-expansion property of the projection operator hold for all definitions of norm?

Question

For convex problem, of course. I vaguely remember this holds for weighted norm also. But I am curious if there are some general conclusions about what kinds of norm will fit in this framework?

Answer 1

Here is a synthetic (i.e non-analytic) response to guide you.

The projection operator $P_C$ onto a closed convex set $C \subseteq \mathbb R^n$ is the resolvent of the normal cone $N_C : x \mapsto N_C(x) := \{g \in \mathbb R^n | \langle v, z - x\rangle \le 0\} = \partial i_C(x)$. That is, $P_C = (Id + N_C)^{-1}$. $N_C = \partial i_C$ is maximally monotone (Rockafellar '76), and $P_C$ is firmly non-expansive. Now for another mm operator $F$, you can consider the $F$-resolvent of $N_C$, namely the operator $(F + N_C)^{-1}F$. This is going to be $F$-firmly nonexpansive, in a sense detailed in section 4 of this paper by HHB. This is a generalization because taking $F = \mathrm{Id}$, one recovers the usual projection. This construction covers things like: defining the prox as we did in the begining, but replace the $\ell_2$-norm by the norm induced by a positive-definite matrix, etc.