GPS Always Overestimates Distances | Hacker News Reader

GPS Always Overestimates Distances

i-programmer.info

86 pointsisp21 comments

That was a painfully bad explanation of why random errors cause an over-estimate of distances. There's a much better visual explanation:

Suppose you have the true location for both points. Draw a circle with a center at the first point that goes through the second. Replace the second point with a circular distribution of errors around the original location. Any error outside the original circle increases the measured distance, while any error inside the original circle decreases it. More points are going to be outside the circle, since that's the direction it curves.

This explains a qualitative feature about the formula given - that the error tends towards zero as the distance between two points increases. It also maps well with the case where d approaches zero, where any measurement is simply the result of the random effect.

I think both this explanation and the one in the article are correct, but ignore the fact that GPS distance measurements typically are made by summing the distances between many correlated noisy position measurements.

[GPS devices must use frequent position measurements because approximating a continuous real path by line segments will underestimate the length of curved paths]

Because of that, the largest contribution to the summed error of the distance between points A and B does not occur when the position of B is erroneously measured at a position B' that is farthest from A. Reason is that, likely, the next measurement will happen when the GPS device is at a position C such that B is roughly halfway between A and C. That means B' lies in the direction of C, and the distance between C' and B' will be smaller than that between C and B, correcting for the measurement error between B and A.

Because of that I think it is more insightful to describe the measured path as randomly zigzagging around the actual path. For any reasonably smooth real path such a zig-zag path will be longer than the real path. Even if the real path zigzags around a lot, it is very, very unlikely that the measurement errors happen to undo the zigzagging.

[paper at http://www.tandfonline.com/doi/full/10.1080/13658816.2015.10..., by the way]

I think my explanation, your zig-zag one, and the article's are describing the same thing with slightly different emphasis. The zig-zag is what you get when you compose a bunch of what I'm visualizing together, and it's the sort of thing that gets worse when you add more measurements of shorter distances. Balancing it is the corner-cutting effect which gets better with more measurements (which the paper you linked describes as "interpolation" which it intentionally did not analyze).

Thank you for this post; I wish there were more like it. You used incisive logic to critique and explained another, better way of understanding the idea.

Random errors need not be unbiased errors. Otherwise I think you have am intuitive answer,

Nice. Great job.

This article assumes there is no filter used, and it makes a lot more sense to use a filter. Years back when I was doing this, we could set the filter constants to over smooth the line and cut corners or to undersmooth it for more zig zag and over shooting corners. We would set it on each device (back in the days of feature phones) so it gave as accurate measurement as possible for typical usage. It worked out pretty well.

The graphs in the article show that sometimes GPS underestimates the distance. It is merely more likely that it will overestimate.

For each individual measurement yes, but given repeated measurements on a path statistically you'll almost always end up with an overestimation.

I've never had cause to use one, but isn't this what a Kalman filter is for? Does is not solve this problem without other measurement sources?

https://en.m.wikipedia.org/wiki/Kalman_filter

Tl;Dr: sideways errors add up, lengthways errors cancel.

This is not hard to understand: a wobbly line is longer than a straight line. That's all.

Assuming >2 points, your explanation holds. ThrustVectoring's explanation holds for the case of 2 points as well.

Doesn't this imply that all measured distances (GPS or otherwise) are overestimated, to the extent that the measurements have any uncorrelated variance?

Only distances that are calculated by taking two (noisy) position measurements and calculating the displacement between the positions.

If you're summing up directly measured ranges, there shouldn't be a statistical bias.

All measurements have noise, you should still see this effect if you use a steel ruler, just scaled down to the noise of temperature fluctions changing the length of the ruler.

If you use the ruler to directly measure the distance between subsequent points, the random temperature fluctuations will be as likely to increase as decrease the measured distance (of course for a real steel ruler, this would be dominated by the systematic error in the ruler's markings, which will accumulate over summed measurements).

If instead you used the ruler to measure (X, Y) co-ordinates of each point, then calculated the displacement between the points from those co-ordinates, the random errors would have a bias towards lengthening the path as in the article.

Information here is useful in understanding the limitations of GPS accuracy, as well as looking at some of the ways to improve it (I say some as I didn't see GLONASS mentioned).

http://www.gps.gov/systems/gps/performance/accuracy/

I was expecting this to be known / obvious for people who do paths and distances from GPS. Of course two separate point measurements cannot be corrected, but that's not what sports apps are doing - if you're collecting the whole path, there are multiple ways to smooth it and get better results. Even downsampling + curve fitting could help.

Isn't the distribution of the errors roughly known? If so then couldn't one just subtract the mean error in the distance caused by this from each line segment, and end up with something much closer?

This seems relevant to real life. E.g. if you're Uber, you gotta figure out how to correct for that. Neat.

Reply on news.ycombinator.com