2

This is a followup to a question I asked in this thread. I'm posting separately so points can be awarded.

Hopefully someone can help me with a reference for this problem, or the construction. I have a metric defined on $n$ points in $\mathbb{R}^2$. What are sufficient conditions to be able to find a higher dimensional Euclidean space so that you can place $n$ points in such a way that these distances are attained with the standard metric? If it is possible, is there a formula of some sort to determine the locations (up to rigid motions)? I understand that is very general and hopefully someone knows of a weak enough set of conditions that it works for the application I have in mind.

To make it more explicit: If $\{x_i\}$ are the original points with distances $d(x_i, x_j)$ and $\{y_i\}$ are the images in $\mathbb{R}^N$, find $y_i$ such that $$|y_i - y_j| = d(x_i, x_j)$$

The linked thread proves it cannot be done in general.

Community
  • 1
muaddib
  • 8,267

1 Answers1

1

For the existence of an isometric embedding into a Euclidean space

there's a necessary and sufficient characterization: the squares of the distances must be of negative type: specifically, given the $D_{ij} = d^2_{ij}$ values, then they must satisfy the inequality $$ \sum_{i,j} b_i b_j D_{ij} \le 0$$ for all real $b_i$ such that $\sum_i b_i = 0$. All of this is discussed rather well in the book by Deza and Laurent.

The quote is from this answer by Suresh Venkat.

The aforementioned theorem is due to Schoenberg: see Metric spaces and positive definite functions. The actual computation of an embedding is addressed, among others, by a 1985 paper Solution of the embedding problem and decomposition of symmetric matrices (Sippl, Scheraga).

Community
  • 1