# Recover unknown vectors with dot-product queries

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

• 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. – Gerhard Paseman Jun 1 at 0:10
• Why is this presented as one problem, as opposed to $n$ completely separate problems? – Steven Landsburg Jun 1 at 0:38
• @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. – Joseph O'Rourke Jun 1 at 0:41
• @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$. – Joseph O'Rourke Jun 1 at 0:57
• 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$. – Josiah Park Jun 1 at 6:12