Viktor Korotynskiy, Czech Institute for Informatics and Cybnernetics at Czech Technical University in Prague
Tuesday, June 27, 2023 - 11:00am to 12:00pm
PDL C-401
Galois/monodromy groups attached to parametric systems of polynomial equations provide a method for detecting the existence of symmetries in solution sets. Beyond the question of existence, one would like to compute formulas for these symmetries, towards the eventual goal of solving the systems more efficiently. I will describe one possible approach to this task using numerical homotopy continuation and multivariate rational function interpolation. I will illustrate this approach on practical examples of minimal problems in computer vision. Since minimal problems in computer vision are represented by polynomial systems with a lot of variables (more than 30 including the parameters), the straightforward dense multivariate interpolation is problematic for even small degrees since it generates large Vandermonde matrices. I will show that minimal problems in computer vision have a lot of scaling symmetries (in both unknowns and parameters) and explain how they can be used to significantly reduce the size of Vandermonde matrices when interpolating the symmetries that fix the parameters. This is joint work with Timothy Duff, Tomas Pajdla and Margaret Regan.