# The Probabilistic Method Exercise 2.7.8

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

• What is $r$ in $k/2r < 1$? Commented Oct 25, 2019 at 15:35
• I think $r$ can be any integer as long as $k/2^r < 1$ and $2^r \leq n$. I also wanted to add that my original question had a typo: $k/2r$ should be $k/2^r$. Commented Oct 25, 2019 at 21:26

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