How the $l_1$, $l_2$ and $l_\infty$ norms are they linked together?

Question

Suppose I have a vector $x \in \mathbb{R}^n$ such that $||x||_1=C$ for some $C \geq 0$ and suppose $x$ contains no negative entries i.e. $x_i \geq 0 \; \forall i$. Let's call $\mathcal{D}$ this set of vectors satisfying such conditions.

I am looking for a vector $x \in \mathcal{D}$ with maximum $l_2$ norm. I know that $||x||_{\infty}\leq ||x||_2 \leq ||x||_1$. I also know through convex optimization that the point $x=\frac{e}{n}$ with $e$ a all-ones vector, is the one of minimum $l_2$ norm. So, is that true to say that the vector of $\mathcal{D}$ with maximum $l_2$ norm is such that it has all components, but a single one equal to $C$, equal to $0$ ?

More generally, is that true to say that on $\mathcal{D}$, as $||x||_{\infty}$ increases, $||x||_2$ also increases ? In other words, if I take two vectors $x^{(0)}$ and $x^{(1)}$ belonging to $\mathcal{D}$ such that $||x^{(0)}||_\infty \leq ||x^{(1)}||_\infty$, does it imply $||x^{(0)}||_2 \leq ||x^{(1)}||_2$. I would appreciate an answer which holds for any $n$

Thanks, it would help me

Answer 1

So, is that true to say that the vector of $\mathcal{D}$ with maximum $l_2$ norm is such that it has all components, but a single one equal to $C$, equal to $0$ ?

Yes.

If I take two vectors $x^{(0)}$ and $x^{(1)}$ belonging to $\mathcal{D}$ such that $||x^{(0)}||_\infty \leq ||x^{(1)}||_\infty$, does it imply $||x^{(0)}||_2 \leq ||x^{(1)}||_2$?

The answer to this is yes, and the following two facts will suffice.

Lemma 1: Let $x = (x_1,\dots,x_n) \in \mathcal D$ with $x_1 \geq x_2 \geq \cdots \geq x_n$. For notational convenience define $x_{n+1} = 0$. Fix an index $1 < j \leq n$. For any $t \in [0,\max\{x_j-x_{j+1},x_{j-1}-x_j\}]$, define $y = x + t(e_{j-1} - e_j)$ where $e_i$ denotes the $i$th standard basis vector. Then $y$ is an element of $\mathcal D$ with entries in descending order, and $$ \|x\|_2 \leq \|y\|_2. $$

Proof: Note that $$ \|y\|_2^2 - \|x\|_2^2 = \\ (x_{j-1} + t)^2 + (x_j - t)^2 - x_{j-1}^2 - x_j^2 =\\ 2x_{j-1}t + t^2 - 2x_j t + t^2 =\\ 2(x_{j-1} - x_j + t)t \geq 0. $$

Lemma 2: Suppose that $x,y \in \mathcal D$ are such that $x_1 \geq \cdots \geq x_n$ and $y_1\geq \cdots \geq y_n$ with $y_1 \geq x_1$. Then there exists a sequence of vectors $y_0,y_1,\dots,y_k \in \mathcal D$ with $y_0 = x, y_k = y$, and each $y_j$ can be attained from $y_{j-1}$ as in Lemma 1.

This is a tricky proof to write out, but the intuition is clear if you try it out for a low-dimensional example.

Induction on the number of entries in $x$ and $y$ that fail to agree (with a base case of two such entries) will make the proof go nicely.

Now, the desired result:

Proposition: If $x,y \in \mathcal D$ are such that $\|x\|_\infty \leq \|y\|_\infty$, then $\|x\|_2 \leq \|y\|_2$.

Proof: Let $\tilde x$ be $x$ rearranged so that the entries of $x$ are in descending order, and let $\tilde y$ be similarly defined. There exists a sequence of vectors $y_0,\dots,y_k$ with $y_0 = \tilde x$ and $y_k = \tilde y$ satisfying the construction in Lemma 2. By Lemma 1, it follows that $$ \|x\|_2 = \|\tilde x\|_2 = \|y_0\|_2 \leq \|y_1\|_2 \leq \cdots \leq \|y_k\|_2 = \|\tilde y\|_2 = \|y\|_2 $$ as desired.

Answer 2

Too long for a comment, made community wiki.

---

THIS PART IGNORES THE CONSTRAINT ON $\lVert x\rVert_1=1$, so it does not answer the question.

The fact that "as $\|x\|_\infty$ increases, $\|x\|_2$ also increases", whatever that means, is false. Take for example $x_1=(\frac{1}{\sqrt 2}, \frac{1}{\sqrt 2})$ and $x_2=(1, 0)$. The $\infty$ norm of $x_1$ is smaller than the one of $x_2$, but the $2$ norm is the same for both.

---

With the constraint on $\|x\|_1$ the best thing to do is parametrize $$ x=t,\qquad y=1-t,\qquad t\in [0, 1].$$ So, $$ \|x\|_\infty= \max(t, 1-t), \qquad t\in [0, 1], $$ while $$ \|x\|_2=\sqrt{ 2t^2-2t+1}, \qquad t\in [0, 1].$$