Let $P$ be a set of $n+t$ ($t > 0$) points in $\mathbb{R}^n$ and $M = (m_{i,j})_{i,j=1, \dots, n}$ be the matrix containing all measured pairwise euclidean distances between point $p_i$ and point $p_j$ with an additional normally distributed error $e \sim \mathcal{N}(0, \vartheta)$.

What is the best estimate of the coordinates of the points?

My idea

Without loss of generality, $p_1 = (0, \dots, 0)$ and $p_2 = (0, m_{1,2}, 0, \dots, 0)$. $p_3$ then is on the hypersphere around $p_1$ with distance $m_{1,3}$ and on the hypersphere around $p_2$ with the distance $m_{2,3}$. I could calculate a position of the next point with circle-circle intersection, but then I have the problem that I didn't take care of the errors

  • $\begingroup$ Notice that just knowing distances cannot give you the absolute point coordinates. They are only defined up to a rigid transformation. $\endgroup$ – Yves Daoust Apr 27 '19 at 16:00
  • $\begingroup$ I notice that you can't find the absolute position (hence the first "wlog" in "my idea") and also any rotation (hence the "wlog" for p2). Hence basically once the coordinates are found, they can still be rotated / moved. $\endgroup$ – Martin Thoma Apr 27 '19 at 16:16
  • $\begingroup$ what is a rigid transformation? $\endgroup$ – Martin Thoma Apr 27 '19 at 16:16
  • $\begingroup$ I guess that to need to fix the first point, express that the second point belongs to a fixed line from the first point, the third point belongs to a fixed plane by the first two, and so on, each time increasing the degrees of freedom. $\endgroup$ – Yves Daoust Apr 27 '19 at 16:24

I will break down the problem to a problem in which we have a point $p$ and we have measured the distances $d_i$ to $p$ from the points $q_i$ for $i=1,..., N$.

then we can formulate the equations

$$d^2_1=[p-q_1]^T[p-q_1]+\varepsilon_1$$ $$d^2_2=[p-q_2]^T[p-q_2]+\varepsilon_2$$ $$\vdots $$ $$d^2_N=[p-q_N]^T[p-q_N]+\varepsilon_N$$

Then we can try to estimate the position $p$ by using the least squares estimate $\hat{p}$ by minimizing the cost function $F$ (this is equivalent to minimizing the sum of squared errors)

$$F(p,q_1,q_2,...,q_N)=\sum_{i=1}^{N}\left[d^2_N-[p-q_i]^T[p-q_i] \right]^2.$$

You do this for all your points then you update the distance matrix and try to run the same algorithm again to obtain a better estimate. You can also directly update the distances after calculating the first point and so forth to improve the convergence of the algorithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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