Using Galois Theory to prove optimality of solutions to geometric problems in Vision
Prof. Richard Hartley (RSISE, Australian National University)
MSI Computational Mathematics Seminar SeriesDATE: 2009-02-09
TIME: 11:00:00 - 12:00:00
LOCATION: JD G35
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
Galois Theory provides a method for establishing that a problem can not be solved by a 'machine' that is capable of the standard arithmetic operations, extraction of radicals (that is, $m$-th roots for any $m$), as well as extraction of roots of polynomials of degree smaller than $n$, but no other numerical operations.
The method is applied to two problems well known in geometric Computer Vision, five point calibrated relative orientation, which can be realized by solving a tenth degree polynomial, and two-view triangulation, which can be realized by solving a sixth degree polynomial. It is shown that both these solutions are optimal in the sense that an exact solution intrinsically requires the solution of a polynomial of the given degree (10 or 6 respectively), and cannot be solved by extracting roots of polynomials of any lesser degree.
An extension of these methods also rules out the possibility of solving these problems more simply using the Singular Value Decomposition, which is the preferred method of solution for many other geometric problems.
This rules out the possibility of undiscovered structure in the problems that might allow a simpler solution. It also follows that neither of these problems can be solved in closed form.
BIO:
http://users.rsise.anu.edu.au/~hartley/
