M.Sc Student | Pan Dror |
---|---|

Subject | On the Solution of the GPS Localization Problem |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Amir Beck |

Full Thesis text |

We consider the
problem of localization of a user's position using a finite set of its *pseudo-ranges
*from a set of satellites. The pseudo-ranges are subjected to some unknown *clock-bias
*and other unknown noise. Two formulations of the problem as optimization
problems are being considered: the nonlinear *least squares *formulation
and the nonlinear *squared least squares *variant. The least squares
problem is nonsmooth and nonconvex, whereas the squared least squares problem
has a smooth objective function, although also nonconvex.

Both problems
are shown to have tight connection to the well known *circle fitting *problem,
which is in fact, identical to a private case of them. We show that a
relaxation of the squared least squares problem is equivalent to a *generalized
trust region subproblem*, and therefore can be solved efficiently. We show a
simple algorithm for solving it using a procedure for finding roots of a
univariate equation. Sufficient conditions for both problems to attain a global
minimum are derived. In the circle fitting least squares problem, there is also
a tight connection between the attainment condition to the known *orthogonal
regression* problem. Finally, a fixed point method for solving the least
squares problem is introduced and analyzed. The squared least squares solution
is used as an initial guess for it. The quality of the solutions obtained from
both problems are tested numerically, using standard Monte-Carlo simulations.