2
$\begingroup$

Suppose there are $n$ unknown unit vectors in $\mathbb{R}^d$, $V=\{v_1,\ldots,v_n\}$, no two identical. Your task is to determine the vectors in $V$. The only tool at your disposal is to query a particular vector $v_i$ and learn what is its dot product with your query vector $v$, which $v$ is your choice. So your query will return $v \cdot v_i$.

My question is:

Q. What is the best strategy to uniquely determine $V$, where "best" is the fewest number of queries, almost surely, as a function of $n$ and $d$?

"Almost surely" is to avoid choosing a query vector identical to one of the unknown vectors.


Example. $n=3$, $d=2$. Let the unknown vector be $V=\{v_1,v_2,v_3\}$ with \begin{eqnarray} v_1 & = & (1,0) \\ v_2 & = & (0,1) \\ v_3 & = & \left( \frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}} \right) \end{eqnarray} $v_3$ is $(1,1)$ normalized to unit length. Let's say we choose just one $v=(-1/2,1)$ normalized as our query vector: $$ v=\left( -\frac{1}{\sqrt{5}},\frac{2}{\sqrt{5}} \right) $$
          Arrows
Then we could query with $v \cdot v_i$: \begin{eqnarray} v \cdot v_1 & = & -\frac{1}{\sqrt{5}} \\ v \cdot v_2 & = & \frac{2}{\sqrt{5}}\\ v \cdot v_3 & = & \sqrt{\frac{2}{5}}-\frac{1}{\sqrt{10}} \end{eqnarray} Knowing these dot products, and that $|v_1|=|v_2|=|v_3|=1$, we have $6$ unknowns and $6$ equations, and indeed the original $\{v_1,v_2,v_3\}$ constitute a solution. But only one of eight solutions, e.g.: \begin{eqnarray} v_1 & = & \left( -\frac{3}{5}, -\frac{4}{5} \right) \\ v_2 & = & \left( -\frac{4}{5}, \frac{3}{5} \right) \\ v_3 & = & \left( -\frac{7}{5 \sqrt{2}}, -\frac{1}{5 \sqrt{2}} \right) \end{eqnarray}

So which and how many additional queries are needed to pin down uniquely the unknown $V$? One may use many different query vectors, if that's advantageous; above I just used one, $v$.

$\endgroup$
  • $\begingroup$ There is the obvious strategy involving nd queries with a known orthonormal frame. Indeed, one needs nd queries in this case unless one finds some components of the mystery vectors are zero: any nonzero unknown could appear with positive or negative sign. Gerhard "Almost Surely ND Are Best" Paseman, 2019.05.31. $\endgroup$ – Gerhard Paseman Jun 1 at 0:10
  • $\begingroup$ Why is this presented as one problem, as opposed to $n$ completely separate problems? $\endgroup$ – Steven Landsburg Jun 1 at 0:38
  • $\begingroup$ @StevenLandsburg: Feel free to concentrate on specific $n$ & $d$. I am hoping that considering all as variants of the same general question will clarify. And I wouldn't want to proliferate questions unnecessarily. $\endgroup$ – Joseph O'Rourke Jun 1 at 0:41
  • 2
    $\begingroup$ @StevenLandsburg: I see... Have to think about this. I meant a single query to be $v \cdot v_i$. Because there is freedom to choose different query vectors $v$, it seems conceivable that intelligent choice of query vectors reduces the total number of queries. But perhaps I am wrong, and it all reduces to determining one $v_i$. $\endgroup$ – Joseph O'Rourke Jun 1 at 0:57
  • 1
    $\begingroup$ As was mentioned, for generic $V$, the problem just boils down to considering each $v_i$ separately. The points in $V$ would need to be structured in order to be able to infer what $V$ is with less 'measurements' $\langle v,v_i \rangle$, $v\in\mathbb{R}^d$. $\endgroup$ – Josiah Park Jun 1 at 6:12

Your Answer

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

Browse other questions tagged or ask your own question.