Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

> Naturally, large range uncertainty increases the ambiguity of position, but the relative position of the satellites also matters. If they aren’t well spread, the exactness of calculated location also suffers.

(see the excellent example in OP)

Fun tidbit, the resulting error is known for the system in closed form as Geometric Dilution of Precision, and is a 3x3 (edit: or 4+x4+ if you are estimating bias or quantities like time, thx brandmeyer) matrix that depends on all the locations of the visible sats, and your position relative to them.

GDOP is a general relationship for any estimator based only on the equations used to derive something from sensor remote sensor measurements. It's possible to derive GDOP for any sensing system using the Fisher Information Matrix (which is the inverse of GDOP). Some minor caveats apply, but in general this is a useful trick.

FIM is worth learning if you want to get into sensing & estimation. https://en.wikipedia.org/wiki/Fisher_information

Another fun thing: FIM can be derived a number of ways, and appears if you simply ask (mathematically) "What is the most likely position of the gps sensor given sat locations" as the hessian matrix of the system that you use while answering that question using e.g., convex minimization.

All of sensing & estimation is just mostly convex optimization.



The natural expression of the DOP matrix is 4x4, since the receiver is computing a solution in 4D space-time. Its pretty common for the dominant eigenvector to be along the time-vertical axis for a terrestrial receiver.


Great point, thanks. I edited.


You and I have definitively a different notion of what is fun ;)


Geometric quality is easy to consider in terms of using trig and measured angles to solve for an (roughly) equilateral triangle vs a triangle with a very small measured internal angle.

Also, it's easier to understand variables vs uknowns of GPS if you consider that direct measurement is of velocity and/or acceleration, and position is the resultant derivative, after taking into account the probabilities of various solutions.

(Velocity and acceleration can be measured directly without making as many assumptions about various starting conditions.)


Do you know a good source to learn about the FIM?

(Postgraduate level stats/maths, mostly applied, tiny bit pure.)


For these kinds of problems, literature has multiple derivations of FIM for the purposes of tracking & estimation (and path planning for sensing -- my former specialty). Shameless plug: https://josh.vanderhook.info/media/pdf/thesis.pdf chapter 3.

Most of that was distilled from literature or basic math (and probably contains errors -- thanks grad school).

Bishop https://www.sciencedirect.com/science/article/pii/S000510980... was always a good reference for me,

as was

B. Grocholsky, “Information-theoretic control of multiple sensor platforms,” Ph.D. dissertation, University of Sydney. School of Aerospace, Mechanical and Mecha- tronic Engineering, 2006

And here's a tutorial that might help:

https://www.sciencedirect.com/science/article/abs/pii/S00222...


Interferometry isn't convex, even the kernel trick won't save you. I don't think...


In my experience, the usual trick is to do a few iterations of "linearize and solve the new convex problem". Sometimes, you can get super clever and use LM: https://sites.cs.ucsb.edu/~yfwang/courses/cs290i_mvg/pdf/LMA...

Look there in equation 6: That's the FIM being left multiplied when solving these types of problems. (under standard gauss-newton step, which is also common)

Another tidbit: If you apply matrix inversion lemma to eq 6, you can get the (Extended)Kalman Filter update steps. Somewhat related: https://robotics.stackexchange.com/questions/1180/informatio...


Why is it called "Geometric Dilution of Precision" and not "covariance matrix"? In what ways is the former not the latter?


GDOP is sometimes taken to mean the largest eigenvalue or trace of the covariance matrix. It's a metric for the badness of the estimate.

Often, GDOP is broken into components HDOP, VDOP, etc for the values corresponding to some earth-fixed coordinate frame. That starts to look more like statistics about the covariance matrix.

Here's a derivation: https://en.wikipedia.org/wiki/Dilution_of_precision_(navigat...

Here, it ends up being (usually) the sqrt(trace(covariance))




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: