Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $a$ be a vector in $R^m$, such that $\sum_{i=1}^ma_i=0$ I would like to bound $\sqrt{2m(2m-1)}\|a\|_{\infty}$ by $\sqrt{2m}\|a\|_2$ (or other way arround with the sharp constants), in the case when vector $a$ is compressible and when vector $a$ is incompressible:

(Here is definitions of the compressible and incompressible vectors I use: If we consider $R^{\sigma^c}=\mathsf{span}\{e_i: i\in\sigma^c\}$, $\sigma\subset\{1,...,m\}$, $|\sigma^c|=M$.

$x \in \mathsf{Comp}(M, \rho)$ iff there exists $\sigma$ with $|\sigma^c|\leq M$, s.t. projection $|P_{\sigma}x|\leq \rho$.

$x \in \mathsf{Incomp}(M, \rho)$ iff for any $\sigma$ with $|\sigma^c|\leq M$, s.t. projection $|P_{\sigma}x|> \rho$.

I wanted somehow to control $l_{\infty}$ norm. I guess I can do it only with incompressible vectors. But what can we say about compressible vestors?)

share|cite|improve this question
I'm confused about the definitions. What is $\sigma^c$ ? – Suresh Venkat Mar 30 '12 at 15:43
Sorry, buy $\sigma^c$ I've denoted the complement of the set $\sigma\subset\{1,...,m\}$. – David Mar 30 '12 at 16:42
I don't see why you even need that, since $|\sigma^c| \le M$ implies $|\sigma| \ge m - M$. Also, what is $P_\sigma$ ? Please make the question more readable if you wish to get an answer. – Suresh Venkat Mar 30 '12 at 16:46
It was mensioned in the question: by $P_{\sigma}$ I've denoted projection onto set $\sigma$. – David Mar 30 '12 at 16:50
what norm is used in $|P_\sigma x|$? also what are you hoping to prove? if the only thing you know about $x$ is that it is in $\mathsf{Comp}(M, \rho)$ than it could be the case that $\|x\|_\infty = \|x\|_2$. – Sasho Nikolov Mar 30 '12 at 19:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.