2

Suppose we have two points $p_1$ and $p_2$ in a metric space with $\bf{unknown}$ dimensionality, with no way to directly compute the distance between them, e.g. no coordinates.

Say we can randomly sample a set of points $P$ in this space. And say we can calculate the distance between any pair of points in $P$, the distance between any point in $P$ and $p_1$, and the distance between any point in $P$ and $p_2$.

The question I have is: can the distance between $p_1$ and $p_2$ be estimated using points in $P$ and the distances we can calculate with them? Is there some triangulation scheme that would work, without knowing dimensionality? Even if the distance cannot be calculated with certainty is there some statistical estimate? Relatedly, are there restrictions we can place on the space that make this problem tractable?

Any guidance or feedback would be deeply appreciated. Thank you very much.

Update 1: The best I can think is the difference in the distances between a point in $P$ and points $p_1$ and $p_2$ is a lower bound on the distance between $p_1$ and $p_2$. But this seems like a very weak bound. Any further thoughts would be appreciated. Any direct estimate would be amazing.

Update 2: A concrete example is as follows. Say there are two satellites and we can measure distances between known ground locations and each satellite. What is the distance between the satellites? The one difference is we want a procedure that works regardless of the dimensionality of the space.

CambridgeStudent
  • 97
  • What about the metric space in which the distance between any two points is 1? – Ethan Bolker Aug 02 '22 at 01:23
  • Lets say this problem does not use that space, and restrict to a euclidean space of unknown dimension. – CambridgeStudent Aug 02 '22 at 01:27
  • @CambridgeStudent Is it a finite-dimensional space? – D. Dmitriy Aug 02 '22 at 01:31
  • Yes, finite dimensional – CambridgeStudent Aug 02 '22 at 01:31
  • @CambridgeStudent Doesn't triangulation also require that you know something about the angles between your points? I think otherwise the best you can do is put bounds on the distance between the two points of interest. – Charles Hudgins Aug 02 '22 at 04:08
  • if you know distances between the "reference" points of the triangulation, you should be able to get away with not needing angles. the trouble here is you need to know the dimensionality to know how many reference points to use, but in my case, the dimensionality is unknown – CambridgeStudent Aug 02 '22 at 04:11
  • @CambridgeStudent Is that really true? Can you demonstrate it with a 2d example? – Charles Hudgins Aug 02 '22 at 04:13
  • Nevermind. On thinking about it (and googling) you just need to minimize a function as done here – Charles Hudgins Aug 02 '22 at 04:15
  • in 2d, consider 3 reference points. we know the distances between each of the 3 points and $p_1$, so we know where $p_1$ is because it sits at the intersection of 3 circles. same for $p_2$. thus you can calculate the distance between $p_1$ and $p_2$. – CambridgeStudent Aug 02 '22 at 04:15
  • @CharlesHudgins that question you linked to is a different setting: there we know the locations of the reference points, here we do not. thanks for thinking about this and your input – CambridgeStudent Aug 02 '22 at 04:18
  • @CambridgeStudent I was referring more to the general idea of writing down a function like $F(y) = \sum_i (d(x,p_i) - d(y, p_i))^2$ and minimizing, but I can see how with no notion of coordinates that would be more circular than helpful. – Charles Hudgins Aug 02 '22 at 04:27
  • @CambridgeStudent This paper addresses a similar question without as much loss of generality as you might think since you could use the isometric embedding discussed therein to work with coordinates for some number of your points at once. That said, based on some research, it seems this might be a research level question and more suited for math overflow. Before taking your question to math overflow, though, I would advise looking through the literature to see what's already been done. – Charles Hudgins Aug 02 '22 at 04:51
  • thanks a lot @CharlesHudgins, will look into that paper. one thing that needs consideration is if an embedding strategy would work if the dimension is not known. i.e. if too few dimensions are chosen for the embedding space, optimization may not converge. if too many dimensions, there would be several equally good global optima – CambridgeStudent Aug 02 '22 at 16:55

0 Answers0