Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Trilateration

Linear Equations > Applications > Trilateration
alt text 

In many applications such as GPS it is of interest to infer the location of an emitter (for example, a cell phone) from the measurement of distances to known points. These distances are obtained by estimating the differences in time of arrival of a wave front originating from the emitter. In trilateration, only three points are used. We then have to find the intersection of three spheres. The problem can then be reduced to solving a linear equation followed by a quadratic equation in one variable. The multilateration problem, which allows for more than three points, provides more accurate measurements. (Source.)

Denote by x^i, i=1,2,3 the three known points and by R_i the measured distances to the emitter. Mathematically the problem is to solve, for a point x in mathbf{R}^3, the equations |x-x^i|_2^2 = R_i^2, i=1,2,3. We write them out:

x^Tx - 2x^Tx^i + |x^i|_2^2 = R_i^2, ;; i = 1,2,3.

Let t := (1/2)x^Tx. The equations above imply that

t - x^Tx^i = gamma_i := (1/2)(R_i^2-|x^i|_2^2), ;; i = 1,2,3.

Using matrix notation, with X = [x_1,x_2,x_3] the matrix of points, and mathbf{1} the vector of ones:

X^Tx = t mathbf{1} - gamma.

Let us assume that the square matrix X is full-rank, that is, invertible. The equation above implies that

x = x(t) := X^{-T}( t mathbf{1} - gamma).

In words: the point lies in a line passing through x^0 := -X^{-T}gamma and with direction v:=X^{-T}mathbf{1}.

We can then solve the equation in t: x(t)^Tx(t) = 2t. This equation is quadratic in t:

(v^Tv) t^2 + 2 ((v^Tx^0) -1) t + |x^0|_2^2 = 0

and can be solved in closed-form. The spheres intersect if and only if there is a real, non-negative solution t. Generically, if the spheres have a non-empty intersection, there are two positive solutions, hence two points in the intersection. This is understandable geometrically: the intersection of two spheres is a circle, and intersecting a circle with a third sphere produces two points. The line joining the two points is the line { x(t) ::: t in mathbf{R} }, as identified above.