(Note: I posted this question on stackexchange but was told it might be more suited for mathoverflow. There has been some discussion about the problem there.)
Let $U \subset \mathbb{R}^n$ be a $d$-dimensional linear subspace and let $\gamma(U) = \max_{i \in \{1, \ldots, n\}} ||\mathcal{P}_U e_i||^2$ where $\mathcal{P}_U$ is the orthogonal projection onto $U$.
My question is the following: does there exist an orthonormal basis $\{v_j\}_{j=1}^d$ such that: $$\gamma(U) \le \sum_{j=1}^d ||v_j||_{\infty}^2 \le O(\textrm{polylog}(d)) \gamma(U)$$
Some comments:
- The inequality on the left hand side is trivial.
- I know of a construction for any subspace $U$ that is spanned by a collection of standard basis vectors. This construction hinges on the existing of Hadamard Matrices of order $2^k$ for $k \in \mathbb{N}$. I do not see how to generalize this.
- One idea is to use randomness. Heuristically speaking, Let $V \in \mathbb{R}^{n\times d}$ be an orthonormal basis for $U$ and let $R \sim \mathcal{N}(0, 1/d I_{d^2 \times d^2})$ be a random gaussian matrix. $R$ looks almost like an isometry so we could consider looking at $V' = VR$. I can show that with probability $\ge 1-\delta$ $$\max_{i,j} |V'_{ij}| \le C\sqrt{\frac{\gamma(U)\log(nd/\delta)}{d}}$$ which gives the bound except with a $\log n$ factor.
