Question

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

$||A||_{C,\infty} = min _{x \in C} \ \ \ ||A x|| _{\infty}$

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.

Answer 1

The answer is negative. You can achieve at most $O(\sqrt{n\log n})$.

Since more than half of the $\pm 1$ vectors are in $C$,

$$\|A\|_{C,\infty} \leq 2 Aver(\|Av\|_\infty),$$

where the Average is taken over all $\pm 1$ vectors.

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$.

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