# A problem about matrix

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

• Sorry, I'm not sure I understand correctly: are you trying to ask if we can find the sides of an $n$-dimensional cube by sampling $O(n^k)$ vertices, with probability tending to 1 as $n$ goes to $\infty$? ($k$ here is fixed.) Commented Feb 10, 2023 at 8:59
• yes, the probability as long as it's not negligible. Commented Feb 10, 2023 at 9:07
• $\forall i,j$ should be $\forall i\neq j$ ? Also I'm not sure what $[v_1,\dots,v_n]\mathbb{Z}^n$ means.
– YCor
Commented Feb 10, 2023 at 9:34
• yes,$i \neq j$.$\left[\boldsymbol{v}_{\boldsymbol{1}}, \ldots, \boldsymbol{v}_{\boldsymbol{n}}\right] \mathbb{Z}^n$ means a lattice which generate by $\boldsymbol{v}_{1}, \ldots, \boldsymbol{v}_{n}$ . Commented Feb 10, 2023 at 9:43
• \mathcal doesn't work (for me) on MO anymore. It's been like this for weeks. Commented Feb 10, 2023 at 14:00

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.