- [[#Overview]] - [[#The Pseudorange of a Satellite]] - [[#Common GPS Equation Assumptions]] - [[#The Non-Linear Equation]] - [[#The One-Dimensional Case]] - [[#Adding in the Clock Offset]] - [[#Converting to Three Dimensions]] - [[#Linearize the Pseudorange Equation]] - [[#Least Squares Method]] - [[#In Sum]] - [[#Resource: ]] - [[#Connections | Questions:]] ## Overview The GPS constellation has upwards of 30 active satellites (SV) 20,000 km away in a Medium Earth Orbit (MEO) with the first launching around 1980. GPS is used to determine a receiver’s position and clock offset (that is, the delta between the receiver’s time and GPS time). Specifically it determines four unknowns which are the user’s $x, y, z$ and $b_u$. Based on an SVs transmission, the receiver can determine the distance from itself to the SV, called the **pseudorange** (_pseudo-_ because the range includes the clock offset). Since there are four unknowns, the receiver requires four pseudoranges to determine the receiver’s position and clock bias. However, the equations are nonlinear and must be linearized to be solved with standard matrix algebra. In the real world there are errors associated with the pseudorange and thus the solutions are inaccurate, there is said to be residual error in the solution. These residuals can be greatly decreased by using more than four SVs to solve the pseudorange. There are typically 8-12 usable SVs in a clear sky for any given receiver. This leads to a new challenge of having more equations than unknowns (an overdetermined system). There is still residual error in the pseudoranges of the overdetermined geometry matrix, and the way to minimize the errors is to find the smallest value of the sum of the squares of the residuals matrix. That is, find the **least squares solution.** ## The Pseudorange of a Satellite ### Common GPS Equation Assumptions The GPS signal travels at the speed of light, about $c=3 \times10^8$ m/s. This constant is implied when needed in the GPS equations. Therefore equations can have terms that are a mixture of distance or time because they can always be swapped between each other by invoking the speed of light. The position variables $x, y,z$ are sometimes truncated to $x$ to reduce equation width. When this happens, it is implied that $y$ and $z$ get operated on in the same way as $x$. ## The Non-Linear Equation ### The One-Dimensional Case An SV transmits its ephemeris data (of which its position can be derived) to a receiver. Assuming the receiver and SV have no clock offset, the time it takes for the signal to reach the receiver can be calculated by taking the time the SV timestamped its message $t^{(k)}$ versus the time that the user received it $t_u$. A one-dimensional plot would look something like this: ![[4 - Attachments/image 22.png|image 22.png]] The user’s location $x_u$ is determined by adding the SV’s location $x^{(k)}$ to the distance travelled over time. $x_u=x^{(k)}+ c(t_u-t^{(k)})$ ### Adding in the Clock Offset Receivers are not perfect and thus its clock will have an error $b_u$. The time the user receives the SV signal becomes $t_u+b_u$ where $b_u$ is any real number. $x_u=x^{(k)}+ c\big((t_u+b_u)-t^{(k)}\big)$ The pseudorange (dropping the implied speed of light) for a one-dimensional equation works out to be: $\tau^{(k)}=(x_u-x^{(k)})+b_u$ The equation now has two unknowns $x_u$ and $b_u$, so a second SV is needed to solve the set of linear equations. ### Converting to Three Dimensions $y$ and $z$ can be added into the pseudorange by taking the norm, that is, the square root of the sum of the squares of the coordinates (the 3D Pythagorean equation). $\tau^{(k)}=\sqrt{(x_u-x^{(k)})^2+(y_u-y^{(k)})^2+(z_u-z^{(k)})^2}+b_u$ There are now four unknowns and thus four SVs are needed, however this equation is no longer linear. ## Linearize the Pseudorange Equation The pseudorange is linearized by _assuming_ a location $x_0$ and then solving for the delta. The range to the assumed location is called the theorange $r_u^{(k)}$. The satellite is 20,000 km away which means the theo- and pseudorange are sufficiently in parallel and thus they have the same **unit vector.** $\tau_u^{(k)}-|r_u^{(k)}|=-\bold{G}\cdot(\delta x+b_u)$ $\bold{G}$ is the geometry matrix that contains one row of unit vectors for each SV, more generally: $y=\bold{G}\cdot x$ ![[4 - Attachments/image 1 10.png|image 1 10.png]] The angle $\theta$ can be solved as: $\cos{\theta}=\frac{-(x^{(k)}-x_0)}{r_u}$ Where: - $x_0$ is the assumed location of the receiver - $r_u=\sqrt{(x^{(k)}-x_o)^2+(y^{(k)}-y_o)^2+(z^{(k)}-z_o)^2}=||\bold{r}_u-\bold{x}_0||$ is the unit vector from the SV to the assumed location With $\theta$, $a$ can be solved: $a=(x_u-x_0)\cdot\cos{\theta}$ This ends up looking like the equation stated above where: - $a=\tau_u^{(k)}-|r_u^{(k)}|$ - $(x_u-x_0)=\delta x$ - $\bold{G}=\cos{\theta}$ - For $x$ in this example, but in 3D space it is the line-of-sight unit vector from the receiver’s assumed location to the SV This equation holds for when there are exactly 4 SVs in view because $\bold{G}$ is a 4x4 matrix and there are 4 unknowns $x,y,z$ and $b_u$. However when there are more than four, the equations will not produce the same solutions due to measurement error. ### Least Squares Method The Least Squares method finds the best-fit solution by minimizing the sum of squared differences between the observed and assumed pseudoranges. With real-world uncertainty, and more than four SVs, it is not trivial to determine which combination of SVs will produce the most accurate results. ![[4 - Attachments/image 2 5.png|image 2 5.png]] For the overdetermined system, no exact solution can be found to the general pseudorange equation, which means approximations must be made. Atmospheric, clock, and other real-world errors introduce residuals. If a different subset of 4 SVs are chosen, it would most likely result in getting a slightly different position and clock solution. In the ideal case, $0=\bold{G}x-y$, but due to real-world errors, the equation leaves residuals. **The Least Squares** method attempts to minimize the sum of the least squared residuals $||\bold{G}x-y||^2$ (sum of the squares of each of element in the resulting matrix). **Least Squares Derivation** To solve for this least squares, the derivative of the least squares is set to 0 (this will find the minimum point of the residuals function). The least squared residuals can be expanded to: $||\bold{G}x-y||^2=(\bold{G}x-y)^T(\bold{G}x-y)=\bold{G}^Tx^T\bold{G}x-y^T\bold{G}x+y^Ty-\bold{G}^Tx^Ty$ Now take the derivative and set to 0 $\frac{d}{dx}(x^T\bold{G}^T\bold{G}x-2y^T\bold{G}x+y^Ty)=2\bold{G}^T\bold{G}x-2y^T\bold{G}$ $0=\bold{G}^T\bold{G}x-\bold{G}^Ty$ It can then be rearranged to isolate for $x$ $x=(\bold{G}^T\bold{G})^{-1}\bold{G}^Ty$ Therefore the receiver position and time can be solved using the **Moore-Penrose pseudoinverse** $(\bold{G}^T\bold{G})^{-1}\bold{G}^T$ for the overdetermined geometry matrix. ## In Sum GPS determines a receiver’s 3D position and clock offset using signals from satellites. Each satellite provides a **pseudorange**—a range measurement that includes clock error. To solve for the four unknowns ($x, y, z, b_u)$, at least four satellites are needed. In practice, more satellites are available, creating an **overdetermined system**. Because real-world measurements include noise, the **least squares method** is invoked to find the best-fit position by minimizing the sum of squared residuals in the pseudorange equations. ## Resource: - [https://www.youtube.com/watch?v=tqFq6kKhgWs&list=PLGvhNIiu1ubyEOJga50LJMzVXtbUq6CPo&index=13&ab_channel=LaintalAy](https://www.youtube.com/watch?v=tqFq6kKhgWs&list=PLGvhNIiu1ubyEOJga50LJMzVXtbUq6CPo&index=13&ab_channel=LaintalAy) ![[Connect#Connect]]