Assume that $\boldsymbol{v}\_{\boldsymbol{1}}, \ldots, \boldsymbol{v}\_{\boldsymbol{n}} \in \mathbb{R}^n$ satisfy $\forall i, j \in[n],i \neq j,\left\langle\boldsymbol{v}\_{\boldsymbol{i}}, \boldsymbol{v}\_{\boldsymbol{j}}\right\rangle=0,\left\|\boldsymbol{v}\_{\boldsymbol{i}}\right\|=1$. Let $\mathcal{L}=\left[\boldsymbol{v}\_{\boldsymbol{1}}, \ldots, \boldsymbol{v}\_{\boldsymbol{n}}\right] \mathbb{Z}^n$.


The problem is the following: for any polynomial $p$ given $\boldsymbol{B}$ (a basis of $\mathcal{L}$ ) and $\boldsymbol{x}\_1, \ldots, \boldsymbol{x}\_{p(n)}$, each $\boldsymbol{x}\_{\boldsymbol{i}}=t\_{i 1} \boldsymbol{v}\_1+\ldots+t\_{i n} \boldsymbol{v}\_{\boldsymbol{n}}$, where $t\_{i j} \in\{-1,+1\}$ are chosen uniformly at random. The goal is the output $v\_1, \ldots, v\_n$.



A problem about matrix
Nice question!
First of all, notice that the most we can hope for is to get $v\_i$ up to a permutation and $\pm 1$. Besides these obvious obstructions, the answer is yes.




---


The $x\_i$ are independent and identically distributed, and thus all the information about the $x\_i$ comes from taking functions $f : \mathbb{R}^n \to \mathbb{R}$ and computing the expected value of $f(x\_i)$ by taking the average over many $x\_i$. So, our strategy will be to take certain functions $f$ and compute this average by sampling the $x\_i$. Ideally, $f$ would behave nicely with respect to addition because our $x\_i$'s are given as sums of many variables. Thus, it makes sense that $f(x) = g(\langle x, v \rangle)$ for some vector $v$ and some function $g : \mathbb{R} \to \mathbb{R}$ which behaves nicely with respect to addition.


The most obvious choice would be a linear function, which for obvious reasons does not give any information.


Another logical choice would be $g(x) = c^x$. This might be doable, but there is a technical problem here that the variance is very large, so it is hard to get a reliable estimate by sampling. Thus, our next choice is polynomials..


Let $g(x) = x^k$. Then, $g(\langle x\_i, v \rangle) = \left( \sum\_j t\_{i1} \langle v\_i, v \rangle \right)^k$. Expanding out, we see that $g$ consists of a sum of monomials in $\langle v\_i, v \rangle$ with coefficients with the corresponding $t\_{i1}$'s. Taking the expected value, we see that the only terms that remain are those where each $t\_{i1}$ appears to an even power. In particular, there is no reason to look at $k$ odd.


For $k = 2$ the expected value of $g$ is $\sum\_j \langle v\_j, v \rangle^2 = \langle v, v \rangle$, so we get no new information. Thus, we need to take $k = 4$.


For $k = 4$ we basically get $\sum\_j \langle v\_j, v \rangle^4$. Note that both the expected value and the variance are $n^{\Theta (1)}$ and thus with a polynomial number of samples we can compute the expected value to high accuracy. Replacing $v$ with $v + t u$, and taking $5$ values of $t$ we see that we can compute $\sum\_j \langle v\_j, v \rangle^s \langle v\_j, u \rangle^{4 - s}$ for $0 \leq s \leq 4$. In particular taking $s = 1$ we can compute $\sum\_j \langle v\_j, v \rangle \langle v\_j, u \rangle^3 = \langle \sum\_j \langle v\_j, u \rangle^3 v\_j, v \rangle$.


In particular, letting $v$ run over the standard basis vectors we see that we can compute $\sum\_j \langle v\_j, u \rangle^3 v\_j$. Iterating this process $r$ times, we get the vector $\sum\_j \langle v\_j, u \rangle^{3^r} v\_j$. Notice that this vector very quickly becomes proportional to $v\_j$, where $j$ is such that $\lvert \langle v\_j, u \rangle \rvert$ is largest, and thus we get a good approximation for $v\_j$.


Do this $n \log n$ times with different random starting vectors $u$ until (by the coupon collector's problem) we will end up with good guesses for all $v\_j$. From this it is easy to find the $v\_j$ exactly, because for each $x\_i$ we can find out what $t\_{ij}$ is by taking the scalar product with our guess for $v\_j$ and checking the sign, and then we just get a problem in linear algebra.




---


As I've mentioned above, each average can be computed to high accuracy with a polynomial number of samples, and we compute this things a polynomial number of times, thus this whole process requires a polynomial number of vectors $x\_i$. With a small amount of effort this can be made explicit and I think the constants involved should be quite small.


