3
$\begingroup$

Let $x, x_0\in\mathbb{R}^n$ be two vectors satisfying $$\frac{\|x\|_1}{\|x\|_2}\leq\frac{\|x_0\|_1}{\|x_0\|_2}.$$ $\| \cdot\|_1$ and $\| \cdot\|_2$ are the $\ell_1$ and $\ell_2$ norm in $\mathbb{R}^n$, respectively. Suppose that $$\|x_0\|_0:= |\{1\leq i\leq n: (x_0)_i\neq 0\}|=s.$$

The questions is: Does there exist a constant $c$ independent of $n$ and $s$ such that $$\frac{\|x-x_0\|_1}{\|x-x_0\|_2}\leq c\sqrt{s}?$$

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I will uncomfortable with the statement. Would you, please, write down the quantifiers like $\ \forall_{x_0\in\mathbb R^n}\ $ and $\ \forall_{x\in\mathbb R^n}\ $ and $\ \exists_{c}\ $ explicitly (as a part of a logical statement in $\ x_0\ x\ s\ c\ $)? $\endgroup$
    – Wlod AA
    Commented Oct 17, 2019 at 2:42
  • $\begingroup$ Let $f(x)=||x||_1\||x||_2$. We have $f(x)\leq f(x_0)\leq \sqrt{x}$. The result would follow if we could prove that $f$ is convex. $\endgroup$
    – user35593
    Commented Oct 17, 2019 at 16:11
  • $\begingroup$ Two typos: it should be / and $\sqrt{s}$ $\endgroup$
    – user35593
    Commented Oct 17, 2019 at 16:13
  • $\begingroup$ The function can not be convex since we have local maxima$ for example at $(1,...,1)$ $\endgroup$
    – user35593
    Commented Oct 17, 2019 at 16:16

0

Reset to default

You must log in to answer this question.