A Note on Global Positioning System (GPS) and Euclidean Distance Matrices

A. Y. Alfakih · 2025

Read A Note on Global Positioning System (GPS) and Euclidean Distance Matrices by A. Y. Alfakih (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04358.txt.

Introduction

Alfakih writes, in a solo 2025 note, on a cleanup task that sits under GPS fixes. A set of points in space yields a matrix of pairwise distances, and such a matrix must meet strict shape rules. Noise in the raw readings can break those rules. His task: given a sound distance matrix and one noisy row of distances, find the closest row that keeps the enlarged matrix sound at the same embedding dimension.

The task grows out of fault checks in GPS, where a bad reading must be flagged and fixed fast. He gives a criterion that spots when a fault is there at all. He then gives three algorithms to find the fix row. One suits the small case of four points. Two more cover five points and up. The note keeps its scope tight: one matrix, one row, exact dimension held.

Catalog record

CREATORA. Y. Alfakih
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-04358

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Note on Global Positioning System (GPS) and Euclidean Distance Matrices A. Y. Alfakih Abstract Let D D be an n × n n\times n Euclidean distance matrix with embedding dimension r r ; and let d m ∈ ℝ n d^{m}\in\mathbb{R}^{n} be a given vector. In this note, we consider the problem of finding a vector y ∈ ℝ n y\in\mathbb{R}^{n} , that is closest to d m d^{m} in Euclidean norm, such such that the augmented matrix [ 0 y T y D ] \left[\begin{array}[]{cc}0&y^{T}\\ y&D\end{array}\right] is itself an EDM with embedding dimension r 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 n=4 , and two for the case n ≥ 5 n\geq 5 . AMS classification: 51K05, 93B27, 15B99, 90C20. Keywords: Global positioning system, Euclidean distance matrices, quadratically constrained quadratic programming. 1 Introduction Recently, several publications [ 3 , 11 , 10 ] employed Euclidean distance matrices (EDMs) to address various problems related to the Global Positioning System (GPS). This note follows in the spirit of these works, aiming to highlight the potential usefulness of EDMs theory in the mathematics of GPS. EDMs have found applications across a range of fields, including molecular conformation theory [ 7 ] , the statistical theory of multidimensional scaling [ 4 ] , wireless sensor networks [ 12 ] , and the rigidity theory of bar-and-joint frameworks [ 2 ] . The Global Positioning System (GPS) is a satellite-based navigation system that allows users to determine their position anywhere on Earth. It consists of a constellation of at least 24 operational satellites distributed across six orbital planes, at an altitude of about 20,200 km above Earth’s surface. These satellites are arranged to ensure that at least four are visible from any point on Earth’s surface at all times. Let \rho^{m}_{i} denote the pseudorange to satellite i , i.e., the measured distance between the receiver and satellite i . The pseudorange \rho^{m}_{i} differs from the true geometric range \rho_{i} due to factors such as clock synchronization error, atmospheric effects, relativistic effects and other sources of error (e.g., multipath, receiver noise, etc.). Relativistic and atmospheric errors can be effectively corrected using established models and techniques. However, clock error arising from unsynchronized satellite and receiver clocks, and random error such as those caused by receiver noise or multipath effects, are more difficult to correct. Due to their unpredictable nature, these errors can significantly degrade positioning accuracy. Effectively mitigating them is essential for enhancing the overall accuracy and reliability of GPS-based systems. Thus, we can assume that (\rho^{m}_{i})^{2}=(\rho_{i})^{2}+\epsilon_{i}, where \epsilon_{i} is the error associated with satellite i assumed to be orders of magnitude smaller than (\rho_{i})^{2} . This motivates the following problem. Let p^{1},\ldots,p^{n}\in\mathbb{R}^{r} , with n\geq r+1 , denote the known positions of n satellites, 1 1 1 Although in the actual GPS problem the dimension is r=3 , we prefer to maintain generality by using arbitrary r . and assume that p^{1},\ldots,p^{n} affinely span \mathbb{R}^{r} . Let d^{m}=(d^{m}_{i}=(\rho^{m}_{i})^{2})\in\mathbb{R}^{n} , be a given vector, and define the n\times n matrix D=(d_{ij}) by d_{ij}=||p^{i}-p^{j}||^{2}, (1) where ||.|| denotes the Euclidean norm. Thus D is an EDM of embedding dimension r . The goal is to find the vector y\in\mathbb{R}^{n} closest to d^{m} in Euclidean norm, and then to determine the receiver’s position q\in\mathbb{R}^{r} , such that y_{i}=||q-p^{i}||^{2} for i=1,\ldots,n . In other words, we seek to solve the optimization problem \underset{y}{\min} ||y-d^{m}||^{2} subject to \left[\begin{array}[]{cc}0&y^{T}\\ y&D\end{array}\right] is an EDM of embedding dimension r . (2) Once the optimal solution y^{*} is found, the receiver’s position q can be recovered via a simple formula. We present three algorithms for solving ( 2 ): one for the case n=4 , and two for the case n\geq 5 . In addition, we provide a necessary and sufficient condition for d^{m} to be self-consistent, meaning that y^{*}=d^{m} is already the optimal solution of problem ( 2 ). It is worth noting that the receiver’s position q , and hence y , can also be obtained by solving the following unconstrained nonlinear optimization problem \min_{q}\sum_{i=1}^{n}(||p^{i}-q||^{2}-d^{m}_{i})^{2}. (3) As we will show, for n\geq 5 , the optimality condition of problem ( 2 ) leads to an unconstrained minimization problem equivalent to problem ( 3 ). 1.1 Notation We summarize, here, the notation used throughout this note. e denotes the vector of all 1’s of the appropriate dimension. I is the identity matrix of the appropriate dimension. {\bf 0} denotes the zero vector or the zero matrix of appropriate dimension. For a symmetric matrix A , the notation A\succeq{\bf 0} means that A is positive semidefinite, and A^{{\dagger}} is the Moore-Penrose inverse of A . Finally, ||x||=\sqrt{x^{T}x} denotes the Euclidean norm of x . 2 Euclidean Distance Matrices In this section, we present the results of the theory of EDMs most relevant to this note. For a comprehensive discussion, refer to the monograph [ 2 ] . An n\times n matrix D is called a Euclidean distance matrix (EDM) if there exist points p^{1},\ldots,p^{n} in some Euclidean space such that d_{ij}=||p^{i}-p^{j}||^{2}\mbox{ for all }i,j=1,\ldots,n. These points p^{1},\ldots,p^{n} are called the generating points of D , and the dimension of their affine span is called the embedding dimension of D . Let the embedding dimension of an EDM D be r . We assume that p^{1},\ldots,p^{n} , the generating points of D , lie in \mathbb{R}^{r} and affinely span \mathbb{R}^{r} . Define the n\times r matrix P=\left[\begin{array}[]{c}(p^{1})^{T}\\ \vdots\\ (p^{n})^{T}\end{array}\right], (4) where each p^{i}\in\mathbb{R}^{r} is a row of P . P is called a configuration matrix of D . Since the points p^{1},\ldots,p^{n} affinely span \mathbb{R}^{r} , P has full column rank; i.e., rank P=r . Without loss of generality, we assume that the origin coincides with the centroid of p^{1},\ldots,p^{n} . Thus, P^{T}e={\bf 0}, (5) where e\in\mathbb{R}^{n} is the vector of all 1’s. Let V be an n\times(n-1) matrix such that Q=[e/\sqrt{n}\;\;\;\;V] (6) is an n\times n orthogonal matrix. Clearly, an EDM D is symmetric with zero diagonal, and nonnegative offdiagonal entries. Among the various characterizations of EDMs, the following two are most relevant to our purposes. Theorem 2.1 . [ 8 , 13 , 15 ] Let D be an n\times n symmetric matrix with zero diagonal. Then D is an EDM if and only if (-V^{T}DV) is a positive semidefinite matrix. Moreover, the embedding dimension of D is equal to rank (-V^{T}DV) . The (n-1)\times(n-1) matrix X=-\frac{1}{2}V^{T}DV is called the projected Gram matrix of D . Theorem 2.2 . [ 8 , 13 , 15 ] Let D be an n\times n symmetric matrix with zero diagonal and let d\in\mathbb{R}^{n} . Then, the augmented matrix \left[\begin{array}[]{cc}0&d^{T}\\ d&D\end{array}\right] is an EDM with embedding dimension r if and only if de^{T}+ed^{T}-D is a positive semidefinite matrix with rank r . The Gram matrix of the points p^{1},\ldots,p^{n} is given by B=PP^{T}. (7) Note that our assumption P^{T}e={\bf 0} implies that Be={\bf 0} . Matrix B is positive semidefinite with rank r . The Gram matrix B and the projected Gram matrix X are related by X=V^{T}BV\mbox{ and }B=VXV^{T}. Let B^{{\dagger}} denote the

Read the complete text