A note on Global Positioning System (GPS) and Euclidean distance matrices

Let $D$ be an $n\times n$ Euclidean distance matrix (EDM) with embedding dimension $r$; and let $d\in R^n$ be a given vector. In this note, we consider the problem of finding a vector $y\in R^n$, that is closest to d in Euclidean norm, such that the augmented matrix $\left[\begin{array}{cc}0& y^T\\ y& D\end{array}\right]$ is itself an EDM of embedding dimension $r$. This problem is motivated by applications in Global Positioning System (GPS). We present a fault detection criterion and three algorithms: one for the case $n=4$, and two for the case $n\ge 5$.