Estimating quality of projection

Solution 1:

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).$$