I need your expertise in the understanding the following problem:

Given a convex set $C \subseteq \mathbb{R}^n$, and let $a,b \in C$ such that: $$ a = \arg\max_{x \in C} \left\| x\right\|_2 \\ b = \arg\max_{x \in C} \left\| x \right\|_1$$

Its known that: (same for $b$) $$ \left\| a\right\|_2 \leq \left\| a \right\|_1 \leq \sqrt{n} \left\| a\right\|_2 $$

Is it possible that: $$ \left\| a \right\|_2 > \left\| b \right\|_2 $$

Please advise and thanks in advance.

  • $\begingroup$ What do you understand under $\|\cdot\|_1$ and $\|\cdot\|_2$? Two arbitrary norms, or the usual $\sum_i |x_i|$ and $\sqrt{\sum_ix_i^2}$? $\endgroup$ – TZakrevskiy Apr 24 '17 at 14:13
  • $\begingroup$ Right. I cant think of an example where that occurs i.e. $ \left\| a \right\|_2 > \left\| b \right\|_2$ $\endgroup$ – user3492773 Apr 24 '17 at 14:20
  • $\begingroup$ You can think of $L_1$ as the Manhattan distance and $L_2$ as the euclidean distance. $\endgroup$ – user3492773 Apr 24 '17 at 14:36

Just take two points, $x=(1,0)$ and $y=\left(\frac{0.99}{\sqrt 2},\frac{0.99}{\sqrt 2}\right)$, and let $C$ be a convex hull of these two points.

Clearly, $$\|y\|_2 = 0.99<\|x\|_2=1,\quad \|y_1\|=0.99\cdot \sqrt 2>1=\|x\|_1.$$ Hence $$\arg\max_{z\in C} \|z\|_2 = x,\\\arg\max_{z\in C} \|z\|_1 = y,$$ and $\|y\|_2<\|x\|_2$.

The idea is to look at level sets of your two norms and choose the points where supremums are attained.

  • $\begingroup$ Can we bound the maximum distance between $x$ and $y$ disregarding what $C$ contains (it must be convex though)? $\endgroup$ – user3492773 Apr 24 '17 at 15:24
  • $\begingroup$ @Michael the distance in which norm? Given the symmetry of the norms, I'd say that the best estimation that you can get without additional hypothesis is $\|x-y\|_2\le 2\|x\|_2$. $\endgroup$ – TZakrevskiy Apr 24 '17 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.