I am able to show that any $k$-dimensional subspace of $\mathbf{R}^{Ck\log(k)}$ must contain a unit vector $x$ such that $\|x\|\_{\infty} \ge c\sqrt{1/\log(k)}$ for a small enough constant $c$.


But is there a $k$-dimensional subspace of $\mathbf{R}^{Ck\log(k)}$ such that *every* nonzero vector $x$ in the subspace satisfies $\|x\|\_{\infty} \ge (1/\text{poly}(\log(k)))\|x\|\_2$? And is there any random rotation that can be applied to a given $k$-dimensional subspace such that the subspace obtained after rotating has this property with some constant probability?



Subspaces with all vectors having large $\|x\|_{\infty}/\|x\|_2$ value
Since this hasn't been answered, I think the answer is no.


Indeed, suppose that there exists a $k$-dimensional subspace $V$ of $\mathbb{R}^n$ such that for all $\mathbf{x}\in V$,
\begin{equation}
\frac{\|\mathbf{x}\|\_2}{D}\leq \|\mathbf{x}\|\_{\infty}\leq \|\mathbf{x}\|\_2,
\end{equation}
for some value of $D\geq 1$.
Equivalently, there exists a linear transformation $T:\mathbb{R}^k\to \mathbb{R}^n$ that maps onto $V$ and preserves the $2$-norm (namely, let the columns be an orthonormal basis of $V$), so that this is equivalent to
\begin{equation}
\frac{\|\mathbf{x}\|\_2}{D}\leq \|T\mathbf{x}\|\_{\infty}\leq \|\mathbf{x}\|\_2 \quad\forall \mathbf{x}\in \mathbb{R}^k.
\end{equation}
By considering the rows of $T$, this means there exists $n$ vectors $\mathbf{t}\_1,\ldots,\mathbf{t}\_n\in \mathbb{R}^k$ with at most unit length such that for any vector $\mathbf{x}\in S^{k-1}$,
\begin{equation}
\max\_{i\in [n]} \vert \langle \mathbf{t}\_i,\mathbf{x}\rangle\vert\geq \frac{1}{D}.
\end{equation}


Consider a random vector $\mathbf{X}$ drawn uniformly from $S^{k-1}$. The distribution of $\vert \langle \mathbf{t}\_i/\|\mathbf{t}\_i\|\_2,\mathbf{X}\rangle\vert$ does not depend on $\mathbf{t}\_i$, and by concentration of measure on the sphere, the probability that $\vert \langle \mathbf{t}\_i,\mathbf{X}\rangle\vert$ exceeds $O\left(\sqrt{\frac{\log n}{k}}\right)$ is less than $1/n$ (as $\|\mathbf{t}\_i\|\_2\leq 1$). If $D\leq c\sqrt{\frac{k}{\log n}}$ for some sufficiently small constant $c$, we obtain a contradiction as there exists a vector violating the desired inequality. Therefore, $k\leq CD^2\log n$ for some large enough constant $C$. For your regime of $D=\text{polylog}(n)$, this unfortunately implies a polylogarithmic upper bound on the dimension of $k$.


