1
$\begingroup$

Given two vector sets, $\vec x_i$ and $\vec y_i$ (for $i$=1,2,...N, but the dimensionality of each vector can be more than N), let their sum set be $\vec z_i = \vec x_i + \vec y_i$. It's easy to compute the scalar inter-distances: $x_{ij} = \Vert{\vec x_i-\vec x_j}\Vert$, $y_{ij} = \Vert{\vec y_i-\vec y_j}\Vert$, $z_{ij} = \Vert{\vec z_i-\vec z_j}\Vert$.

But, what's the quickest computation method to go backwards (i.e., from all of the inter-distances to any "high-dimensional embedding")? It seems I'm forced into ugly numerical "trial and error" methods even for small N=4 though there are easy analytical methods (for any N) if I didn't need to match the sum's inter-distances.

$\endgroup$
2
  • $\begingroup$ For a specific example, suppose there are 4 vectors in each set, so all 3 sets could be embedded individually as pyramids in our 3-D space. But, if those 4 vectors each actually consist of 5 numbers, we probably need 4-D to simultaneously embed all 3 objects as a sum. $\endgroup$
    – bobuhito
    Aug 18, 2013 at 3:27
  • $\begingroup$ Presumably you meant: $y_{ij} = \Vert{\vec y_i-\vec y_j}\Vert$. $\endgroup$ Aug 18, 2013 at 15:16

1 Answer 1

1
$\begingroup$

Suppose $y_i=0$ for all $i$. Then $z_i = x_i$, $y_{ij}=0$, $z_{ij}=x_{ij}$, and in this special case, your problem reduces to reconstructing $x_i$ from the interpoint distances $x_{ij} = \Vert{\vec x_i-\vec x_j}\Vert$. This is a known NP-hard problem, as discussed in earlier MO questions ("Difference Sets" and "Feasibility of a list of prescribed distances in R^3"). So I think your problem cannot be easier than this intractible special case.

$\endgroup$
1
  • $\begingroup$ I agree. Though the simpler problem is NP-hard, it's still analytically solvable. This tougher problem, however, is forcing me into numerical solutions. $\endgroup$
    – bobuhito
    Aug 18, 2013 at 16:29

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.