# Statistical ramblings of a Moonbat

I will try to use this medium to talk about my statistical musings

## First world problem of Global Positioning Systems

with one comment

In ancient times, circa AD 2000, getting a GPS device to give you an accurate location was nothing short of a black magic art. After sacrificing three goats, the navigational gods might align at least 3 satellites on your horizon or if they are especially pleased with you for throwing that virgin down the funeral pyre, you might see 4 satellites in your horizon thereby giving you not just the latitude and longitude of your location but an accurate time reference.  Now fast forward 10 years and there are countless countries trying to emulate the highly successful US based GPS with their own navigational satellite constellations. The primary driving force has been the potential for an US based system being used as a bargaining chip on the whim of an US lawmaker (hint ICANN and the internet domain naming controversy). Some of the navigational satellite constellations are:

1. GPS (USA) has 32 satellites,
2. GLONASS (Russia) has around 23 satellites
3. QZSS (Japan) 3 to 4 primarily over Japan,
4. Beidou (China) 16 initially but will expand to 40 eventually,
5. Galileo (EU) final system will have 30 in orbit
6. IRNSS (India) possibly 3, primarily over India .

Add to the above list, numerous ground and satellite based augmentation systems that are useful for correcting any navigational errors. So a GPS receiver in 2013 could potentially be receiving signals from more than 100+ satellites to help find its position. You might assume that all these added information might provide better localization accuracy. However, the reality is quite different. There are two limiting factors. First limitation arises from the reduced memory and processing capabilities within GPS semiconductors which sets an upper limit to the number of satellites that a receiver can search or track at any time. This would be fixed over time due to Moore’s law, but the second issue is much more fundamental and it rests on the algorithms that are used to find your location.

A GPS receiver is essentially measuring the time of flight of a radio wave from a satellite to the receiver. When you multiply this time difference by the speed of light, you get the range, or in GPS parlance, pseudorange between the satellite and your GPS receiver. In addition, the GPS receivers have access to a table of values called ephemeris which helps to accurately compute the position of a satellite at any given time. So using the known position of satellites and the range measurements to them, your receiver has to figure out its own Cartesian coordinate (xy & z). However, there is another hidden parameter that need to be estimated if you care to have a very accurate location. This hidden parameter arises from the cheap clock reference used in your GPS semiconductor. More than likely your GPS semiconductor in you smartphone doesn’t have an atomic clock that is synchronized with the atomic clocks on these navigational satellites. So there would be a clock bias (let’s call it $\tau$) between your receiver and GPS satellites that need to be accounted to get an accurate position. Consequently, there are four parameters (3 Cartesian coordinates and 1 clock bias) that need to be estimated from the pseudorange measurements and the known position of the satellites using a technique called Multilateration. The most popular algorithm used in GPS for Multilateration relies on Taylor series approximation to linearize the state equation that relates the pseudorange to the unknown parameters and subsequently apply least-square solution to get $x, y, z, \tau$. You may read about the details about this computation in this very concise document.

Least-square algorithm is vulnerable to outliers or extremities in measurement. This is because the objective of a least-square algorithm is to find the parameter set (in our case $x, y, z, \tau$) that would result in the lowest sum of square difference between the pseudoranges calculated from x, y and z and the measured pseudoranges from each satellite. Consequently, if there are couple of satellites that are producing some extreme pseudorange values due to either intentional degradation by the host government or due to a fundamental wireless propagation issue called multipath fading, then location estimate by GPS would be inaccurate. I have touched upon this fading previously where it was used to aid indoor navigation.  So in 2013, the accuracy of a GPS receiver is not limited by the number of satellite on its horizon but rather an algorithmic limitation arising from the choice of satellites that it decided to include in its Multilateration algorithm.

First World problem