Lipschitz constant of a vector valued function

Question

I want to find the Lipschitz constant for $f:\mathbb{R}_{+}^{N}\rightarrow\mathbb[0,1]^{N}$, $$ f_{i}(x)=x_{i}\wedge\left[1-\sum_{j=1}^{i-1}x_{j}\right]^{+},i=1,2,\ldots,N, $$ ($a\wedge b=\min(a,b)$ and $\left[a\right]^{+}=\max(a,0))$ with respect to the $L^{1}$ norm, i.e., I want to find $K$ such that $$ \sum_{i=1}^{N}\left|f_{i}(x)-f_{i}(y)\right|\leq K\sum_{i=1}^{N}\left|x_{i}-y_{i}\right|. $$ By looking at examples I think $K$ should be equal to 2 but I'm not sure how to show this. For example, in two-dimensions if we have $x=(0.9,0.3)$ and $y=(1,0.3)$ then $f(x)=(0.9,0.1)$ and $f(y)=(1,0)$ so $\sum_{i=1}^{N}\left|f_{i}(x)-f_{i}(y)\right|=0.2$ and $\sum_{i=1}^{N}\left|x_{i}-y_{i}\right|=0.1$.

Answer 1

Yes, $f$ is $2$-Lipschitz. First, let's consider the sets $$ E_k = \left\{x\in\mathbb{R}_+^N : \sum_{j=1}^{k-1} x_j \le 1,\ \sum_{j=1}^{k} x_j \ge 1\right\},\quad k=1,\dots,N-1 $$ with the convention that $$E_N= \left\{x\in\mathbb{R}_+^N : \sum_{j=1}^N x_j \le 1 \right\}$$ The map $f$ truncates the cumulative sum of $(x_i)$ so that it does not exceed $1$. The restriction of $f$ to $E_k$ is just $$ f(x_1,\dots,x_N) = \left(x_1,\dots, x_{k-1}, 1-\sum_{j=1}^{k-1} x_k, 0 ,\dots,0\right) $$ which is easily seen to be $2$-Lipschitz: the first $(k-1)$ components are $1$-Lipschitz when taken together, and the $k$-th component is $1$-Lipschitz on its own.

The Lipschitz estimates can be glued together as follows. Let $a,b\in \mathbb R^N_+$ and consider the segment $I=[a,b]$. The intersections $I\cap E_k$ are closed in $I$ and cover $I$. By induction on $N$, one can prove that there exists a finite sequence $p_j$ of points on $I$ beginning with $a$ and ending with $b$, so that for each $j$ there is $k$ such that $p_j,p_{j+1}\in E_k$. The triangle inequality completes the proof.