What's the difference between 'non-expansive', and 'sublinear'?

Question

What's the difference between 'non-expansive', and 'sublinear'? How the properties become important?

I saw 'non-expansive' is described as an enjoyable property studying proximal method in convex optimization. Why?

Answer 1

These notions are not related to each over. They are completely disjoint.

Imagine you have a metric space $(X,d)$. Then a map $f:X\to X$ is called non-expansive, if $d\bigl(f(x),f(y)\bigr)\le d(x,y)$ for any $x,y\in X$. This means that the distances between images are not greater than the distances between arguments, so after applying the map $f$ to $x,y$ the distance does not grow. In the other words, non-expansive map is a lipschitzian map with Lipschitz constant $1$.

Now let's have two vector spaces $X,Y$ over $\Bbb R$. The map $f:X\to Y$ is sublinear if $f(x+y)\le f(x)+f(y)$ for any $x,y\in X$ (the subadditivity contidition) and $f(tx)=tf(x)$ for any $x\in X, t\ge 0$ (nonnegative homogeneity condition).

Of course, if $X$ is a metric-vector space (e.g. the normed space) then there is a sense to speak about non-expansive sublinear maps. For instance, $f:\Bbb R\to\Bbb R$ given by $f(x)=|x|$ is nonexpansive and sublinear. Another map, $g(x)=2x$ is linear (so sublinear) and it is not nonexpansive. A sine function is nonexpansive and not sublinear.