4
$\begingroup$

I have a set of $d$-dimensional vectors $V = \{+1, 0, -1\}^d $. Then $P(V)$ constitutes the power set of $V$. I now construct a set of unit vectors $V_{\mathrm{sum}}$ from the power set $P(V)$ such that $$ V_{\mathrm{sum}} = \left\{\frac{\bar{v}}{\|\bar{v}\|} \quad \Bigg| \quad \bar{v} = \sum_{v \in S} v, \quad \forall S \in P(V)\right\} $$ That is, each subset $S \in P(V)$ contributes to a vector in $V_{\mathrm{sum}}$ formed as a sum of all the vectors in the subset $S$ and then taking the unit vector in that direction.

Note that there could be duplicates. For example, for $d = 3$, the vector $(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}})$ can be formed as a sum of vectors of any of the following subsets $$S_1 = \{(1,0,0),(0,1,0),(0,0,1)\},\\ S_2 = \{(1,1,0 ),(1,0,1),(0,1,1)\},\\ S_3 = \{(1,1,1)\}.$$

and many more possibilities.

Now I want to find the maximal isolation of a vector from $\,V_{\mathrm{sum}}\,$ from the remaining vectors of $\,V_{\mathrm{sum}},\,$ i.e. the maximum of Euclidean distance between any vector in $V_{\mathrm{sum}}$ to its closest vector in $V_{\mathrm{sum}}$. Is there an easy way to upper bound this max distance?

In other words, if I consider $V_{\mathrm{sum}}$ to be an $\varepsilon$-net to the surface of the unit ball in $d$-dimensions, then I want to find an upper bound on $\varepsilon$. Any weak upper bound on $\varepsilon$ should suffice. The goal is to show that $V_{\mathrm{sum}}$ forms a better $\varepsilon$-net than the unit vectors formed from the vectors in $V$.

$\endgroup$
5
  • 1
    $\begingroup$ @domotorp, there would be some $\varepsilon$ such that any vector on the surface of the $d$-dimensional unit ball is at a distance at most $\varepsilon$ from one of the vectors in $V_{\text{sum}}$ right? That's the reason I am calling it an $\varepsilon$-net. $\endgroup$ – usercsw May 17 '20 at 8:07
  • 1
    $\begingroup$ What is the motivation behind asking this question? Is there a specific application you have in mind? $\endgroup$ – Pedro Juan Soto May 20 '20 at 5:29
  • $\begingroup$ It is hard to say anything useful for general $S$. Are you looking for a feasible algorithm to compute such an upper bounds (or exact value) or do you have some restrictions on the $S$. In full generality, $|S|$ could be ${v,-v}$ and the maximal isolation is 2. Maybe one can say more if we lower bound $|S|$, but because there are many ways to duplicate vectors this will be probably not too helpful. $\endgroup$ – M. Winter Jun 19 '20 at 7:02
  • $\begingroup$ The "surface of the unit ball" is usually called the "unit sphere". $\endgroup$ – YCor Oct 17 '20 at 7:15
  • $\begingroup$ Purely out of curiosity where did you find this set $V_{sum}$? $\endgroup$ – Christian Chapman Oct 17 '20 at 16:38
2
$\begingroup$

Since the notation quickly becomes cumbersome for any $S \in 2^{V}$ define \begin{equation} v_S \overset{\text{def}}{=} \sum_{v \in S} v, \end{equation} and let \begin{equation} \hat v_S \overset{\text{def}}{=} \frac{v_S}{\|v_S\| }, \end{equation} If we fix a $v_S \in \text{span}(V)$ then the goal is to find/bound \begin{equation} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \end{equation} \begin{equation} = \min_{w \in V_\text{sum}}\left|\frac{1}{\|w_T \| \|v_S \| } \right|\left| \| w_T \| v_S - \|v_S \| w_T \right| \end{equation} and then use that to find/bound the value of \begin{equation} \max_{v_S \in V_\text{sum}}\min_{w_T \in V_\text{sum}} |v_S-w_T| . \end{equation} To that end notice that

  • if $S = \{0\}$ then $\hat v_T$ doesn't make sense so that we can always assume that $\exists v' \in S$ such that $|v'_i|=1 $ (as a matter of fact we can further assume $0 \not\in S$ since it has no effect)
  • furthermore if $\forall v' \in S$ we have that $-v' \in S$ then we have that $v_S = 0$ so that we can also assume that $\exists v' \in S$ such that $-v' \not\in S$
  • taking this idea even further we have that if $ v \in S$ and $- v \in S $ then $v_S = v_{S \setminus \{ v, -v\}}$ and therefore we can assume that $v \in S \implies -v \notin S$
  • generalizing this concept further we have that if $ T \subset S$ and $v_T = 0 $ then $v_S = v_{S \setminus T}$ and therefore we can assume that $(\not\exists T \subset S)(w_T = 0 )$

Therefore if we define the support of $v$ as the following \begin{equation} \text{supp}(v) = \{i \in [n] \ | \ v_i \neq 0\}, \end{equation} we can use the preceding claims to deduce the following:

Lemma $(\forall v_S \in \text{span}(V))(\exists m \in [n])$ such that both

  • $(v_S)_m = \min\{ |(v_S)_i| \ | \ i \in [n] \}$

  • either $e_m \not\in S$ or $-e_m \not\in S$

where \begin{equation} (e_m)_i = \begin{cases} 1 & \text{if } i = m \\ 0 & \text{o.w.}\end{cases} . \end{equation}

(Proof): By the previous claims we can assume W.L.O.G. that $v_S$ is reduced; i.e. \begin{equation} (\not\exists T \subset S)(w_T = 0 ). \end{equation} Let $m$ satisfy $(v_S)_m = \min\{ |(v_S)_i| \ | \ i \in [n] \}$ then by assumption either $e_m \not\in $ or $-e_m \not\in S$. QED

Therefore W.L.O.G. assume that $S$ satisfies the properties above and let $m \in [n]$ the index that satisfies the properties of the lemma and define \begin{equation} T = S \cup \{e_m \}, \end{equation} so that \begin{equation} (w_T)_i = \begin{cases} v_i \pm 1 & \text{if } i = m \\ v_i & \text{o.w.}\end{cases} . \end{equation} Notice that if $\| v_S \|= \sqrt k$ then $\|w_T \|= \sqrt{k \pm \epsilon}$ for some $\epsilon \leq |2v_m + 1|$; therefore we have that \begin{equation} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| \leq \frac{1}{\sqrt k \sqrt{k \pm \epsilon} } \left| \sqrt{k \pm \epsilon} v_S - \sqrt{k} w_T \right| \end{equation} \begin{equation} = \frac{1 }{ \sqrt k \sqrt{k \pm \epsilon} } \sqrt{ \left(\sqrt{k} v_m - \sqrt{k \pm \epsilon}(w_T )_m \right)^2+ ( \sqrt{k \pm \epsilon} - \sqrt{k})^2 \sum_{i \neq m } v_i^2 } \end{equation} \begin{equation} = \frac{1 }{ \sqrt k \sqrt{k \pm \epsilon} } \sqrt{ \left(\sqrt{k} v_m - \sqrt{k \pm \epsilon}v _m \pm \sqrt{k \pm \epsilon} \right)^2+ ( \sqrt{k \pm \epsilon} - \sqrt{k})^2 \sum_{i \neq m } v_i^2 }. \end{equation} But notice that \begin{equation} \left(\sqrt{k} v_m - \sqrt{k \pm \epsilon}v _m \pm \sqrt{k \pm \epsilon} \right)^2 = \end{equation} \begin{equation} = \left(\sqrt{k} v_m - \sqrt{k \pm \epsilon}v _m \pm \sqrt{k \pm \epsilon} \right)^2 -\left(\sqrt{k} v_m - \sqrt{k \pm \epsilon}v _m \right)^2 + \left(\sqrt{k} v_m - \sqrt{k \pm \epsilon}v _m \right)^2 \end{equation} \begin{equation} = 2\left(\sqrt{k} - \sqrt{k \pm \epsilon} \right) \left(k \pm \epsilon \right)v_m + \left(\sqrt{k} - \sqrt{k \pm \epsilon} \right)^2 v_m^2; \end{equation} and therefore have that \begin{equation} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| \leq \end{equation} \begin{equation} \leq \frac{1 }{ \sqrt k \sqrt{k \pm \epsilon} } \sqrt{ 2\left(\sqrt{k} - \sqrt{k \pm \epsilon} \right) \left(k \pm \epsilon \right)v_m + \left(\sqrt{k} - \sqrt{k \pm \epsilon} \right)^2 v_m^2 + ( \sqrt{k \pm \epsilon} - \sqrt{k})^2 \sum_{i \neq m } v_i^2 } \end{equation} \begin{equation} = \frac{1 }{ \sqrt k \sqrt{k \pm \epsilon} } \sqrt{ 2\left(\sqrt{k} - \sqrt{k \pm \epsilon} \right) \left(k \pm \epsilon \right)v_m + ( \sqrt{k \pm \epsilon} - \sqrt{k})^2 \sum_{i \in [n]} v_i^2 } \end{equation} \begin{equation} = \frac{1 }{ \sqrt k \sqrt{k \pm \epsilon} } \sqrt{ 2\left(\sqrt{k} - \sqrt{k \pm \epsilon} \right) \left(k \pm \epsilon \right)v_m + ( \sqrt{k \pm \epsilon} - \sqrt{k})^2 k } \end{equation}

Since $x \geq 0 \land y \geq 0 \implies \sqrt {x+y} \leq \sqrt x + \sqrt y $ we further get that \begin{equation} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| \leq \frac{ \sqrt{\left(\sqrt{k} - \sqrt{k \pm \epsilon} \right) \left(k \pm \epsilon \right)} }{ \sqrt k \sqrt{k \pm \epsilon} }\sqrt{2v_m} + \frac{\left| \sqrt{k \pm \epsilon} - \sqrt{k}\right| }{ \sqrt k \sqrt{k \pm \epsilon} } \sqrt{k}, \end{equation} which W.L.O.G., after possibly relableing $k \leftarrow k-\epsilon$, we have \begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| \leq \frac{ \sqrt{\left(\sqrt{k} - \sqrt{k + \epsilon} \right) \left(k + \epsilon \right)} }{ \sqrt k \sqrt{k + \epsilon} }\sqrt{2v_m } + \frac{ \sqrt{k + \epsilon} - \sqrt{k} }{ \sqrt{k + \epsilon} } \end{equation} \begin{equation} = \left(\frac{\sqrt{\epsilon} }{\sqrt 2 k^{\frac{7}{4}}} + \mathcal{O} \left(\frac{1}{k^{\frac{11}{4}}} \right) \right)\sqrt{2v_m } + \left(\frac{\epsilon}{2k^{\frac{3}{2}}} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) \right) \end{equation} \begin{equation} = \frac{\sqrt{\epsilon} }{\sqrt 2 k^{\frac{7}{4}}} \sqrt{2v_m } + \frac{\epsilon}{2k^{\frac{3}{2}}} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) = \frac{\sqrt{\epsilon} }{ k^{\frac{7}{4}}} \sqrt{v_m } + \frac{\epsilon}{2k^{\frac{3}{2}}} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right). \end{equation} by expanding the Puiseux series. But recall that either $\| v_S \|= k^{\frac{1}{2}}$ or $\| v_S \|= (k+\epsilon)^{\frac{1}{2}}$ (depending on whether we relabeled) by definition so that \begin{equation} |v_m| \leq \frac{1}{|\text{supp}(v_S)|}k^{\frac{1}{2}} \end{equation} by the pigeon-hole principle and therefore \begin{equation} \epsilon < 2|v_m|+1 \leq \frac{2}{|\text{supp}(v_S)|}k^{\frac{1}{2}}+1 \end{equation} and therefore \begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \frac{\sqrt{\epsilon} }{ k^{\frac{7}{4}}} \sqrt{v_m } + \frac{\epsilon}{2k^{\frac{3}{2}}} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) \end{equation} \begin{equation} = \frac{\sqrt{\epsilon} }{ \sqrt{|\text{supp}(v_S)|} k^{\frac{7}{4}}} k^{\frac{1}{4}} + \frac{k^{\frac{1}{2}}}{|\text{supp}(v_S)| k^{\frac{3}{2}}} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) \end{equation}

\begin{equation} = \frac{\sqrt{\epsilon} }{ \sqrt{|\text{supp}(v_S)|} k^{\frac{3}{2}}} + \frac{1}{|\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) \end{equation} \begin{equation} = \left( \frac{2}{|\text{supp}(v_S)|}k^{\frac{1}{2}}+1\right)^{\frac{1}{2}} \frac{1 }{ \sqrt{|\text{supp}(v_S)|} k^{\frac{3}{2}}} + \frac{1}{|\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) , \end{equation} and once again applying the rule $x \geq 0 \land y \geq 0 \implies \sqrt {x+y} \leq \sqrt x + \sqrt y $ we get that \begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \end{equation} \begin{equation} \left( \frac{2}{|\text{supp}(v_S)|}k^{\frac{1}{2}}\right)^{\frac{1}{2}} \frac{1 }{ \sqrt{|\text{supp}(v_S)|} k^{\frac{3}{2}}} +\frac{1 }{ \sqrt{|\text{supp}(v_S)|} k^{\frac{3}{2}}} +\frac{1 }{ |\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) \end{equation} \begin{equation} = \frac{\sqrt{2}k^{\frac{1}{4}} }{ |\text{supp}(v_S)| k^{\frac{3}{2}}} +\frac{1 }{ |\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{3}{2}}} \right) \end{equation} \begin{equation} = \frac{\sqrt{2}}{ |\text{supp}(v_S)| k^{\frac{5}{4}}} +\frac{1 }{ |\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) \end{equation} \begin{equation} = \frac{1 }{ |\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{4}}} \right) \end{equation}

Therefore the bound you are looking for is \begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \frac{1 }{ |\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{4}}} \right) \end{equation}

In particular since $|\text{supp}(v_S)|$ is an integer and $|\text{supp}(v_S)|> 1$ we can weaken this to\begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \frac{1 }{ k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{4}}} \right) \end{equation}

Or recalling that $k = \| v_S \|^2$ we can equivalently right this as \begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \frac{1 }{ |\text{supp}(v_S)| \| v_S \|^2} + \mathcal{O} \left(\frac{1}{\| v_S \|^{\frac{5}{2}}} \right) \end{equation}

and\begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \frac{1 }{ \| v_S \|^2 } + \mathcal{O} \left(\frac{1}{\| v_S \|^{\frac{5}{2}}} \right) \end{equation}

But most importantly we have that the vectors in $V_\text{sum}$ get arbitrarily close for large $n$; i.e. by choosing say $S = \{e_i \ | \ i \in [n]\}$ we have that \begin{equation} \lim_{n \to \infty }\max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \end{equation} \begin{equation} =\lim_{n \to \infty } \frac{1 }{ |\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{4}}} \right) \leq \lim_{n \to \infty } \frac{1 }{ |n| n} + \mathcal{O} \left(\frac{1}{n^{\frac{5}{4}}} \right) = 0 \end{equation}

$\endgroup$
0

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.