I'm having trouble knowing where to start on the following problem:
Let $X$ be a collection of pairwise orthogonal unit vectors in $\mathbb{R}^n$ and suppose the projection of each of these vectors on the first $k$ coordinates is of Euclidean norm at least $\epsilon$. Show that $|X| < k/\epsilon^2$, and this is tight for all $\epsilon^2 = k/2^r < 1$.
It seems like orthogonality makes satisfying the norm condition hard. I have no idea how to use that information though.
Could anybody provide a hint without solving the problem? Thanks in advance :)
The goal is to find a linear combination of those vector such as:
$|$Proj$(\sum r_i v_i,\ \mathbb{R}^k) | > |\sum r_i v_i| = |\sum r_i^2|$
with $r_1, r_2,...r_n \in \mathbb{R}$ and Proj$(w, V)$ is the projection vector of $w$ to the vector space $V$
First, let $\vec{u}$ be a random vector that uniformly chosen out of the unit $k$-sphere.
Now, for each $v_i$, chose $r_i = \cos(\vec{u}, \vec{v_i})$ and denote $L = |$Proj$(\sum r_i v_i, \ \mathbb{R}^k)|$.
Since Proj$(r_i v_i, $span$(u))$ have the same direction as $\vec{u}$
$\mathbb{E}(L) \ge$ $\mathbb{E}(|$Proj$(\sum r_i v_i, $span$(u)|) =\mathbb{E}(r_i^2)|X| \epsilon$
Because $u$ is uniformly chosen out of the unit sphere
$\mathbb{E}(\cos^2(\vec{u},\vec{v_i})) = \mathbb{E}(x_1^2) = \frac{\mathbb{E}(\sum x_i^2)}k = \frac{1}k$ with $(x_1, x_2,...x_k)$ are the coordinate of $\vec{u}$ in $\mathbb{R}^k$
Therefore
$\mathbb{E}(\sum r_i^2) = |X| * \mathbb{E}(r_i^2) = \frac{|X|}k$
$\mathbb{E}(L^2) = \mathbb{E}(L)^2 + var(L) > \mathbb{E}(L)^2 = \frac{|X|^2\epsilon^2}{k^2} $
Which mean $ 1 > \frac{|X|\epsilon^2}k $
I can't construct such vectors for the case where $|X| = 2^r$ but I think their projection vector in $\mathbb{R}^k$ will be uniformly distributed around the $k$ dimensional $\epsilon$ sphere
One probabilistic approach can be considering the probability for an unit vector have Euclidean norm of their projection vector less than $\epsilon$ thereby calculate the expected value for the number of coordinate have such condition over all orthogonal basis of $\mathbb{R}^{|X|}$