Norms over some subspaces - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T00:37:59Z http://mathoverflow.net/feeds/question/49136 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49136/norms-over-some-subspaces Norms over some subspaces Anindya De 2010-12-12T11:44:55Z 2010-12-12T21:15:45Z <p>Let $C$ be the set of all vectors of dimension $n$ such that each of its entries are one of $-1$, $0$ and $1$ and also that the every $v \in C$ has at least $\frac{n}{100}$ $1$'s and at least $\frac{n}{100}$ $-1$'s. For a matrix $A$ (its dimensions are $\Lambda n \times n$ for some sufficiently large constant $\Lambda$), define $||A||_{C,\infty}$ to be</p> <p>$||A||_{C,\infty} = min _{x \in C} \ \ \ ||A x|| _{\infty}$</p> <p>Is it possible to construct an $A$ such that all its entries come from the interval $[-1,1]$ and $||A||_{C,\infty} = n^{1/2 + \epsilon}$ for some $\epsilon>0$. Constructing the matrix $A$ randomly by choosing each of its entries to be independent and uniformly random elements in $[-1,1]$ gets $||A|| _{C,\infty} =n^{1/2}$. The construction does not need to be explicit.</p> http://mathoverflow.net/questions/49136/norms-over-some-subspaces/49140#49140 Answer by Gideon Schechtman for Norms over some subspaces Gideon Schechtman 2010-12-12T13:32:33Z 2010-12-12T21:15:45Z <p>The answer is negative. You can achieve at most $O(\sqrt{n\log n})$.</p> <p>Since more than half of the $\pm 1$ vectors are in $C$, </p> <p><code>$$\|A\|_{C,\infty} \leq 2 Aver(\|Av\|_\infty),$$</code></p> <p>where the Average is taken over all $\pm 1$ vectors.</p> <p>To give an upper bound on $Aver(\|Av\|_\infty)$, note that each of the coordinates of $Av$ has distribution whose tail is subgaussian with parameter $\sqrt n$. By that I mean $Prob(|\sum_ja_{ij}v_j|>C\sqrt n t)\le e^{-t^2}$, for some absolute constant $C$.</p> <p>It follows that the expectation of the maximum of $\Lambda n$ such variables is at most $O(\sqrt{n\log n})$. (Note that independence of these variables is not needed).</p>