|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.