Basis with small $\ell_{\infty}$ norm for Subspace At a high level, I'm interested in finding an orthonormal basis for a $d$-dimensional subspace $U \subset \mathbb{R}^n$ with small entry-wise $\ell_{\infty}$ norm. 
In particular, suppose $v_1, \ldots, v_d$ are the orthonormal basis vectors for $U$.
Let me also write $x_i = (v_{1i}, \ldots, v_{di})^\intercal \in \mathbb{R}^d$ for $i \in \{1, \ldots, n\}$ (i.e. $x_i$ is the $i$th row of the matrix with basis vectors as columns).
Then I would like to prove that:
$
\max_i ||x_i||^2 \le \sum_{j=1}^d ||v_j||_{\infty}^2 \le \max_i ||x_i||^2 O(\textrm{polylog(d)})
$
The first inequality is true regardless of the choice of basis. The second inequality is not true for all orthonormal bases. So can one construct an orthonormal basis $\{v_i\}$ for $U$ such that the above inequality holds?
 A: While I am not sure about general $U$, for $U = \mathbb{R}^n$ the following holds
$$
\sum_j \|v_j\|_\infty^2 \leq C(n) \max_i \|x_i\|_2^2,
$$
for $C(n) = O(\log n)$. If you are willing to believe in the Hadamard conjecture, you can in fact get $C(n) = O(1)$. Of course, this immediately implies the bound for $U$ a coordinate subspaces (i.e. a subspace spanned by standard basis vectors).
The construction is as follows. Let $k = 2^{\lfloor \log_2 n \rfloor}$, and let $v_1, \ldots, v_k$ be the rows of a $k$-dimensional Hadamard matrix, scaled by $k^{-1/2}$ and completed to dimension $n$ with zeros. This gives a basis for $\text{span}\{e_1, \ldots, e_k\}$. Recursively construct a basis for the orthogonal complement, i.e. $\text{span}\{e_{k+1}, \ldots, e_n\}$.
The main observation is that $n-k < n/2$, and the construction is done after at most $\lceil \log_2 n\rceil$ iterations. So, $\sum_j{\|v_j\|_\infty^2} = O(\log n)$ and $\max_i \|x_i\|_2^2 = 1$. 
If the Hadamard conjecture is true, there exists a Hadamard matrix of dimension $4r$ for every positive integer $r$, and then you can just take $k = 4 \lfloor n/4 \rfloor$ in the above construction.
