2
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ 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.) $\endgroup$ Commented Feb 10, 2023 at 8:59
  • 1
    $\begingroup$ yes, the probability as long as it's not negligible. $\endgroup$ Commented Feb 10, 2023 at 9:07
  • $\begingroup$ $\forall i,j$ should be $\forall i\neq j$ ? Also I'm not sure what $[v_1,\dots,v_n]\mathbb{Z}^n$ means. $\endgroup$
    – YCor
    Commented Feb 10, 2023 at 9:34
  • $\begingroup$ 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}$ . $\endgroup$ Commented Feb 10, 2023 at 9:43
  • $\begingroup$ \mathcal doesn't work (for me) on MO anymore. It's been like this for weeks. $\endgroup$
    – Wlod AA
    Commented Feb 10, 2023 at 14:00

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.