<p>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:</p>

<p>(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$.</p>

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

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

<p>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?)</p>

CC BY-SA 3.0
2012-03-30T15:43:03.800Z
I'm confused about the definitions. What is $\sigma^c$ ?
Suresh Venkat
CC BY-SA 3.0
2012-03-30T16:42:11.057Z
Sorry, buy $\sigma^c$ I've denoted the complement of the set $\sigma\subset\{1,...,m\}$.
David
CC BY-SA 3.0
2012-03-30T16:46:05.437Z
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
CC BY-SA 3.0
2012-03-30T16:50:44.587Z
It was mensioned in the question: by $P_{\sigma}$ I've denoted projection onto set $\sigma$.
David
CC BY-SA 3.0
2012-03-30T19:48:07.597Z
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
CC BY-SA 3.0
2012-03-30T21:00:41.733Z
Yes, I am also confused by what $|P_\sigma x|$ means since $P_\sigma x$ is a vector
Suresh Venkat
CC BY-SA 3.0
2012-04-03T02:00:50.630Z
Sorry, it is Eucledian norm.
David
<linear-algebra><it.information-theory><compressed-sensing>
norms of compressible and incompressible vector
David
# norms of compressible and incompressible vector

(Asked by: username_0 on 2012-03-30)

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?)

**Tags:** linear-algebra, it.information-theory, compressed-sensing
> **Comments:**
> **username_1**: I'm confused about the definitions. What is $\sigma^c$ ?  
> **username_0**: Sorry, buy $\sigma^c$ I've denoted the complement of the set $\sigma\subset\{1,...,m\}$.  
> **username_1**: 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.  
> **username_0**: It was mensioned in the question: by $P_{\sigma}$ I've denoted projection onto set $\sigma$.  
> **username_2**: 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$.  
> **username_1**: Yes, I am also confused by what $|P_\sigma x|$ means since $P_\sigma x$ is a vector  
> **username_0**: Sorry, it is Eucledian norm.  

---

## 0 answers

