Non-linear algorithms for least squares measurement problems

Research project This project aims at combining linear estimation theory with non-linear optimization theory to solve non-linear estimation problems found in Photogrammetry and Space Physics.

Many measurement problems of real-world phenomena are solved using linear least squares methods. However, real-world problems are often non-linear, and linear estimation methods generally lack strong convergence properties, something necessary to obtain a solution. On the other hand, non-linear optimization theory, whose methods do guarantee a solution, usually ignore the statistical properties of the problem, something necessary to estimate the quality of the obtained solution. By combining theories from both fields, methods with superior convergence and statistical properties can be constructed. Two application examples are position measurement in images used in photogrammetry and measurements of current sheets in magnetospherical data.

Head of project

Niclas Börlin Associate professor

+46 90 786 68 32

Project overview

Project period:

2008-06-18 – 2009-12-31

Participating departments and units at Umeå University

Department of Computing Science, Faculty of Science and Technology

Research subject

Computing science, Mathematics, Physical sciences

Project description

Many measurement problems of real-world phenomena are solved using
linear least squares methods. If the problem is linear and the measurement errors are normally distributed with known covariance, linear estimation theory suggests how to estimate values from observations. Furthermore, error bounds on the estimates are easily derived. However, many measurement problems are non-linear and must be solved by iterative algorithms. Although first-order error bounds are easily derived, these may not be sufficient near singularities or strong non-linearities. Furthermore, there is the question of whether the algorithm converges or not.

This problem domain is at the intersection of \emph{non-linear}
optimization and \emph{linear} estimation theory. However, linear
estimation theory applied to non-linear problems usually has a
simplistic ``linearize and iterate''-approach that does not guarantee
convergence. On the other hand, non-linear optimization methods
usually focus on guaranteeing convergence, but do not exploit the
statistical properties of the problem. In both cases, the two
techniques are not used to their full combined potential.

Two research areas that would benefit from algorithms with a unified
treatment of non-linear optimization and linear estimation theory are
Photogrammetry and Space Physics.