13
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ @AlexRavsky Indeed. added your comment, thanks! $\endgroup$ – Markoff Chainz May 31 '19 at 8:34
1
+150
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.