Linear Models and Approximations in Personal Positioning

Abstract

If an estimation problem can be modeled with linear equations and normal distributed noise, it has closed form solutions that can be computed efficiently. However, applicability of linear models is limited and when linear models cannot be used nonlinear models are needed. For solving nonlinear models closed form algorithms do not always exist and approximate methods have to be used.

This thesis considers linearity and nonlinearity and it is divided into two main parts along with a background section. In the first part of the thesis I investigate how the measurement nonlinearity can be measured and how the nonlinearity can be reduced. I concentrate on nonlinearity within each prior component of a Gaussian Mixture Filter. The Gaussian Mixture Filter uses a sum of normally distributed components to represent a probability density function. When a nonlinear measurement is used to update the estimate, a local linearization of the measurement function is made within every component. The update of a component results in a poor estimate when nonlinearity within the component is high.

To reduce nonlinearity, the components can be split into smaller components. The main contribution of the first part of the thesis is a novel method for computing the directions of nonlinearity and using this information in splitting a component in such a way that the number of components is minimized while reducing the nonlinearity to a set threshold and approximating the original component well. The applicability of the novel methods introduced in the first part is not restricted to the field of positioning, but they may be applied generally to state estimation with Gaussian Mixture Filters.

In the second part, a different approach for reducing nonlinearity is discussed. Instead of splitting a prior into smaller components to mitigate the effect of nonlinearity, the whole problem is modeled using a linear model. The performance of the linear models compared to nonlinear models is evaluated on three different real-world examples. The linear models are coarser approximations of reality than the nonlinear models, but the results show that in these real world situations they can outperform their nonlinear counterparts.

The first considered problem is the generation of Wireless Local Area Network (WLAN) maps with unlocated fingerprints. The nonlinear models presented use distances between fingerprints and access points, whereas the linear model uses only the information whether a fingerprint and an access point can be received simultaneously. It is shown that when noise level increases, the estimate computed using an iterative method based on the nonlinear model becomes less accurate than the linear model. The noise level resulting in equal accuracies of the linear and nonlinear models is similar to the noise level occurring usually when doing WLAN signal strength measurements.

The second problem discussed is positioning using WLAN. Linear- Gaussian coverage area models for WLAN access points are com- pared with nonlinear parametric and nonparametric WLAN positioning methods. Results show that by using two linear-Gaussian coverage area models for different received signal strengths values the positioning performance is similar or slightly less accurate than with nonlinear methods, but the database size is smaller and the algorithm is computationally less demanding.

Third, I consider the use of linear-Gaussian coverage area models in pedestrian dead reckoning with measurements from an inertial measurement unit. The pedestrian movement is modeled with a linear model and two nonlinear models. The linear model uses only heading change information from an inertial measurement unit, whereas the nonlinear model can use step length measurements in addition. Pedestrian location estimates are solved for the linear model with a Kalman Filter and for the nonlinear model with an Extended Kalman Filter that linearizes the nonlinear state model at the estimate mean. Results show that the linear model has a better accuracy when the uncertainty of heading is large, which is usually the case when the positioning is started.