0
$\begingroup$

Let $x \in R^m$. It is known that $\|x\|_{\infty}\leq \|x\|_2\leq \sqrt m\|x\|_{\infty}$.

What the difference between above inequality and if we are saying that $\|x\|_2\sim \sqrt m\|x\|_{\infty}$?

(we say that $f\sim g$, if $cf \leq g \leq Cf$ for some absolute constants $c,C>0$. Note, f and g may have dimensional dependence).

Why equivalence $\|x\|_2\sim \sqrt m\|x\|_{\infty}$ is not true if vector $x$ is compressible?

(Vector $x$ is k-sparse if the support of the vector $|supp(x)|\leq k$ . Vector is (k,d)-compressible if it is withing Euclidean distance $d$ from the set of all sparse vectors.)

  • 0
    Sorry, I didn't know that the symbol $\sym$ gave different meanings. I've add diffinitions. Thank you very much.2012-03-30

1 Answers 1

2

The difference is that $\|x\|_{\infty}\leq \|x\|_2\leq \sqrt m\|x\|_{\infty}$ contains specific constants, whereas $\|\cdot\|_2\sim \sqrt m\|\cdot\|_{\infty}$, or equivalently $\|\cdot\|_2\sim \|\cdot\|_{\infty}$, merely says that there are such constants. Thus, $\|x\|_{\infty}\leq \|x\|_2\leq \sqrt m\|x\|_{\infty}$ implies $\|\cdot\|_2\sim \sqrt m\|\cdot\|_{\infty}$ but not vice versa.

Regarding the second question, apart from the fact that equivalence of norms is a statement about all vectors and thus it doesn't make sense, strictly speaking, to speak about whether it's true for specific vectors: If you mean that it's only true if we restrict the norm to certain vectors, then that's wrong; the equivalence holds without restrictions, since it's implied by the correct inequality that you give in the first paragraph, which holds for all vectors.