Hacker News Reader

Comment by athenot | Hacker News Reader

With India, China and Russia launching their own positionning systems, I wonder if it would be possible to interpolate an even higher precision by listening to all 5 signals at the same time.

(I don't know enough about signal processing to know if that's a possibility or not.)

View on HN

Not only is it possible, it's already done in many (most?) smartphones made over the past few years, at least for the Russian GLONASS system. As China's BeiDou and Galileo become operational, those will presumably be incorporated too.

However, I'd guess that most of the improvement in user experience comes from the higher reliability than higher accuracy. Even if the errors from all systems were completely uncorrelated (which they are not), averaging the location reported by four systems gives you at most a factor of 2 in improved accuracy. On the other hand, if your chance of being able to lock onto enough satellites (within a given number of seconds) for one system is 80%, the chance that you can lock on to at least one of the four systems becomes 99.8%.

I'm having trouble to grasp how you get a factor 2 improved accuracy if you have data from four uncorrelated systems all having the same accuracy.

Where can I find more information about this?

If your N samples are independent and distributed with the same error sigma, then the error of the averaged result is sigma/sqrt(N). (And of course, sqrt(4) = 2.)

You can calculate this directly by computing the variance of a sum of independent Gaussian random variables. Can't find a great link for further reading, but someone else might be able to help you out.

I'm glad there are people who know what all this means so I can tap a button, say "navigate to the grocery store" to my phone, and not spend brain cycles learning and maintaining knowledge of the wide range of math/programming/engineering specialties I'd otherwise have to master.

Everyone should know the central limit theorem though, simply for its own sake! It's worth the brain cycles :)

https://en.wikipedia.org/wiki/Central_limit_theorem

I had an intuitive sense of this. People saying "half the population has a below average IQ!" always elicited a head tilt from me. I just didn't know there was enough to say on the subject to fill a 8k word wikipedia article.

I'll file this next to the formula I whip up when I want to figure out how much a trip costs based on mileage and fuel prices.

It's sometimes important to actually work out the math to overcome cognitive biases and faulty intuition.

Phrasing the statement as "Think of how dumb an average person you meet on the street is. Now realize that half of all people are even more dumb than that." primes the brain to denigrate the intelligence of a random person, leading to a wrong conclusion.

Another example relates to your formula for fuel economy - some locales use distance-per-volume (miles per gallon) while others use volume-per-distance (liters per 100 km). Intuition may suggest that upgrading from a 15 mpg vehicle to a 20 mpg vehicle is comparable to going from a 30 mpg vehicle to a 35 mpg vehicle - but it's not! Using the reciprocal more accurately describes the emissions and costs related to different fuel economies over the wide range of values that you'll measure in modern vehicles: The example compares a 15.7 -> 11.6 L/100km change and a 7.8 -> 6.7 L/100km change. These units make it much easier to intuit the results.

Doing the math occasionally is a good habit to get into!

The intuition should be that "Half the population has below average X" is untrue for the vast majority of situations, because most real things have a skewed distribution.

AFAIK IQ is a peculiar case because of how IQ is defined.

A lot of natural processes produce results that are normally distributed. So given a large sample, a continuous value range, no bounds (or far away bounds) and a lack of obvious skew the intuition "half the population is below average" has a good chance to be (approximately) true.

Of course IQ is a made up thing that we just defined to behave that way.

Yes, the obvious counter-example is that almost the entire population has more than the average number of legs.

Haha an academic advisor of mine told me once that CLT was the only important thing I had learned that year.

I doubt uncorrelatedness. If the frequencies are very close then the systems share to some degree one source of error: ionospheric lightspeed variations.

In principle, a sufficiently smart device could lock onto one satellite of each system, and in the aggregate they'd be enough. But that would require some serious engineering.

It's not just precision, but availability of the signal and speed. Having more signals in natural and urban canyons improves accuracy and speed when there are more satellites.

One-chip GPS/GLONASS multiconstellation receivers have been on the market for some time. Millions of consumer units sold. Many smartphones have them.

Quad-constellation (GPS, GLONASS, Galileo, BeiDou) receiver chips have been on the market for some time.

For example: STA8090GA, It's automotive Grade GPS/Galileo/Glonass/Beidou/QZSS receiver

http://www.st.com/content/ccc/resource/technical/document/da...

> With India, China and Russia launching their own positionning systems, I wonder if it would be possible to interpolate an even higher precision by listening to all 5 signals at the same time.

First: Only Navstar-GPS, GLONASS and (in near future) Galileo will have worldwide coverage. Perhaps in future (but according to http://www.navipedia.net/index.php/BeiDou_Future_and_Evoluti... not before 2020) BeiDou will also have global coverage. IRNSS only has regional coverage.

So in near future we will only have three sources (not five).

Now for the simple mathematical trick: Model the position of the three systems as normal distributed random variable with same \mu, but different \sigma (\sigma_1, \sigma_2, \sigma_3). These three sigmas have to be measured. Now a convex combination of these random variables is again normal distributed, but with different \sigma (let's call it \sigma^* ) (easy exercise or look it up). Now just compute the coefficients of the convex combination that minimize \sigma^*.

Or you could just say that, for N independently distributed samples, the accuracy improves by a factor of at most sqrt(N) :)

This does only hold if the standard deviation \sigma is the same for all of the normal distributed variables. This is not the case here: Galileo is supposed to be more precise than Navstar-GPS (no surprise, since it is the newer system) - though I know that the US government is working on to increase the precision for Navstar-GPS. On the other hand (source: http://www.navipedia.net/index.php/GLONASS_Performances#GLON...) GLONASS is less precise than Navstar-GPS.

Well, I said "at most", so it holds for all sigma_i. As you know, when the sigma_i are very different, then the accuracy is approximately given by the best accuracy (smallest sigma_i), so there's very little improvement from averaging.

> Well, I said "at most",

OK, you are right. This can indeed be shown.

(warning: armchair expert, I've just read a bunch of wikipedia pages)

I believe there's still sources of systemic error that would affect all the signals similarly, such as atmospheric interference, so even taking (for example) the average of the reported position from all the services may not improve accuracy that much.

https://en.wikipedia.org/wiki/Error_analysis_for_the_Global_... is a good read.

The typical approach seems to be to consider all the visible satellites together (rather than solving for the position indicated by each constellation and averaging them).

So in practice having more satellites means that a good position measurement is possible more of the time.

You can also reduce some of the atmospheric interference by modeling it using both the L1 and L2 signal.

Reply on news.ycombinator.com