# Estimating quality of projection

Suppose we are given a vector $$v$$ and vectors $$\mu_i$$:

$$v = \mu_1+\mu_2+...+\mu_m$$, where $$\mu_i \in R^n$$, all $$\mu_i$$ are of unit length.

Oracle will give me $$k$$ vectors $$\mu_{j_1}, \mu_{j_2},...\mu_{j_k}$$ from the original set such that when I project $$v$$ onto subspace spanned by these vectors the length of the projection is highest possible. In other words, from the set of all combinations of $$k$$ vectors from $$[\mu_1,...\mu_n]$$ the $$[\mu_{j_1}, \mu_{j_2},...\mu_{j_k}]$$ give highest length of projection. Lets denote by $$v_{\text{proj}}$$ projection of $$v$$ onto $$[\mu_{j_1}, \mu_{j_2},...\mu_{j_k}]$$

I want to estimate quality of projection before oracle gives me this $$k$$ vectors. I want to give upper bound on $$||v - v_{\text{proj}}||$$

As far as I understood it is very difficult to obtain these $$k$$ vectors by myself. However, I know that for any two vectors $$\mu_i, \mu_j$$, $$||\mu_i-\mu_j|| \leq \alpha$$, where $$\alpha$$ is a given positive number.

Small values of $$\alpha$$ will tell me that all $$\mu_i$$ are close to each other and heading towards same direction. I would suspect then that projection will be good, and its length will be close to the length of original vector. How can I use this to give an upper bound $$||v - v_{\text{proj}}||$$?

My attempts:

Without loss of generality lets assume that $$k$$ optimal vectors are first $$k$$ vectors in the list, i.e $$\mu_1,\mu_2,...\mu_k$$. Lets denote by $$P$$ projection operator on the space spanned by $$\mu_1,\mu_2,...\mu_k$$.

$$\|v - v_{\text{proj}}\| = \|v - P(v)\| = \|v - P(\mu_1+\mu_2+...+\mu_m)\| =$$

$$\|v - P(\mu_1) - P(\mu_2) - ... - P(\mu_m)\| =$$

$$\| v - \mu_1 - \mu_2 - ... - \mu_k - P(\mu_{k+1}) - P(\mu_{k+2}) - ... - P(\mu_m)\| =$$

$$\|\mu_{k+1} - P(\mu_{k+1}) + \mu_{k+2} - P(\mu_{k+2}) + ... + \mu_{m} - P(\mu_{m})\|$$

$$\|v - v_{\text{proj}}\| \leq \|\mu_{k+1} - P(\mu_{k+1})\| + \|\mu_{k+2} - P(\mu_{k+2}) + ... + \|\mu_{m} - P(\mu_{m})\|$$

$$\|v - v_{\text{proj}}\| \leq (m-k)\alpha$$

So in order to make $$\|v - v_{\text{proj}}\| \leq \epsilon$$, we need $$k \geq \frac{m\alpha - \epsilon}{\alpha}$$

I am not satisfied with this result because $$k$$ grows linearly with $$m$$. I want it to grow much slower, something like $$\log(m)$$. My goal is to show that under some constraints on $$\mu_i$$, we need only approximately $$\log(m)$$ vectors to approximate $$v$$.

I think the bound can be improved substantially. First Cauchy inequality isn't very tight and second, I used $$|\mu_{k+1} - P(\mu_{k+1})\| \leq \alpha$$ which is also very loose.

I am open for additional constraints on $$\mu_1,...\mu_m$$ to achieve logarithmic growth

As Alex Ravsky has noted, we also need a constraint on $$\alpha$$ in order to achieve logarithmic growth. Assume that $$m$$ $$\leq n$$, $$\mu_i$$ is th $$i$$-th standard ort of the space $$\mathbb{R}^n$$, and $$\alpha = \sqrt{2}$$. Then $$\|v - v_{\text{proj}}\| = \sqrt{m-k}$$

• @AlexRavsky Indeed. added your comment, thanks! – Markoff Chainz May 31 '19 at 8:34

In general, the answer is negative. Indeed, assume that $$m\leq n-1$$, $$\alpha\le \sqrt{2}$$ and for each $$i\le m$$, $$\mu_i=\sqrt{1-\tfrac{\alpha^2}{2}}e_{m+1}+\tfrac{\alpha}{\sqrt{2}}e_i$$, where for each $$j$$, $$e_j$$ is $$i$$-th standard ort of the space $$\mathbb{R}^n$$ (that is its $$i$$-th coordinate is $$1$$ and other coordinates are $$0$$).

Let $$\mu_{j_1}, \mu_{j_2},...\mu_{j_k}$$ be any $$k$$ vectors from the original set and $$v_{\text{proj}}=\sum \lambda_i \mu_{j_i}$$. Then $$\|v - v_{\text{proj}}\|^2= \left(1-\frac{\alpha^2}{2}\right)\left(\sum_i \lambda_i-m\right)^2+\sum_i \frac{\alpha^2}{2}(\lambda_i-1)^2+(m-k) \frac{\alpha^2}{2}\ge$$ $$(m-k) \frac{\alpha^2}{2}.$$

We can improve this lower bound as follows.

Put $$\beta=\tfrac{\alpha^2}{2}\le 1$$, $$\Lambda_1=\sum_i\lambda_i$$ and $$\Lambda_2=\sum_i\lambda_i^2$$. Remark that by the inequality between quadratic and arithmetic means, $$\Lambda_2\ge \tfrac{\Lambda_1^2}{k}$$. Then

$$\|v - v_{\text{proj}}\|^2= \left(1-\beta\right)\left(\sum_i \lambda_i-m\right)^2+\sum_i \beta(\lambda_i-1)^2+(m-k) \beta\ge$$ $$\left(1-\beta\right)(\Lambda_1^2-2m\Lambda_1)+ \beta\left(\frac{\Lambda_1^2}{k}-2\Lambda_1 \right)+m^2\left(1-\beta\right) +m\beta=$$ $$\left(1-\beta+\frac{\beta}{k}\right)\Lambda_1^2-2(\beta+m(1-\beta))\Lambda_1+m^2\left(1-\beta\right) +m\beta=$$ $$\left(\sqrt{1-\beta+\frac{\beta}{k}}\Lambda_1-\frac{\beta+m(1-\beta)}{\sqrt{1-\beta+\frac{\beta}{k}}}\right)^2- \frac{(\beta+m(1-\beta))^2}{1-\beta+\frac{\beta}{k}} +m^2\left(1-\beta\right) +m\beta\ge$$ $$-\frac{(\beta+m(1-\beta))^2}{1-\beta+\frac{\beta}{k}} +m^2\left(1-\beta\right) +m\beta=$$ $$\frac{1}{k-k\beta+\beta}(-k(\beta+m(1-\beta))^2 +( k-k\beta+\beta)(m^2 (1-\beta) +m\beta)=$$ $$(m-k) \beta \frac{m-m\beta+\beta}{k-k\beta+\beta}.$$

On the other hand, we can obtain an upper bound for $$\|v - v_{\text{proj}}\|$$ based on the following balancing sum

Lemma (see this answer for references) For any sequence $$\{\nu_1,\dots,\nu_t\}$$ of vectors of $$\Bbb R^n$$ of unit length there exists a sequence $$\{\varepsilon_1,\dots, \varepsilon_t\}$$ such that $$\|\sum_{i=1}^t \varepsilon_i\nu_i\|\le\sqrt{n}$$.

Now we inductively construct a sequence $$\{v_s\}$$ of vectors in $$\Bbb R^d$$ and a decreasing sequence $$\{A_s\}$$ of subsets of $$\{1,\dots,n\}$$ as follows. Put $$A_0=\{1,\dots,n\}$$. Given $$A_s$$, put $$v_s=\sum_{i\in A_s} \mu_i$$. In particular, $$v_0=v$$. By Lemma, there exists a sequence $$\{\varepsilon_i: i\in A_s\}$$ such that $$\|\sum_{i\in A_s} \varepsilon_i\mu_i\|\le\sqrt{n}$$. Let $$A_{s+1}$$ be the smallest of the sets $$\{i\in A_s: \varepsilon_i=1\}$$ and $$\{i\in A_s: \varepsilon_i=-1\}$$. Remark that $$| A_{s+1}|\le |A_s|/2$$. We have $$\|v_s-2v_{s+1}\|=\|v_{s+1}-(v_s- v_{s+1})\|\le \sqrt{n}.$$ Thus

$$\|v_0-2^{s+1}v_{s+1}\|\le \|v_0-2v_1\|+\|2v_1-4v_2\|+\dots +\|2^sv_s-2^{s+1}v_{s+1}\|\le$$ $$\sqrt{n}\left(1+2+\dots +2^s\right)= \sqrt{n}\left(2^{s+1}-1\right).$$

Now pick the smallest $$s$$ such that $$|A_s|\le k$$ (so $$m/2^{s-1}>k$$) and let $$\{j_1,\dots, j_k\}\supset A_s$$. Then

$$\|v - v_{\text{proj}}\|\le \|v_0-2^{s}v_{s}\|\le \sqrt{n}\left(2^{s+1}-1\right)>\sqrt{n}\left(\frac {4m}k-1\right).$$