Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
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. –  bobuhito Aug 18 '13 at 3:27
Presumably you meant: $y_{ij} = \Vert{\vec y_i-\vec y_j}\Vert$. –  Joseph O'Rourke Aug 18 '13 at 15:16
Yes, thanks, I corrected it. –  bobuhito Aug 18 '13 at 16:26

1 Answer 1

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.

share|improve this answer
I agree. Though the simpler problem is NP-hard, it's still analytically solvable. This tougher problem, however, is forcing me into numerical solutions. –  bobuhito Aug 18 '13 at 16:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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