Melvin's digital garden

Art of solving minimal problems

CREATED: 200909281003 Speaker: Tomas Pajdla

** Problem formulation

  • minimal problem: minimum set of matching points to compute correspondence between two images, etc
  • minimal problems can be formulated as set of algebraic equation

** Single variable

  • Construct companion matrix so that characteristic polynomial of the matrix is the equation we want to solve
  • solve the eigenvalue problem using standard methods

** Multiple variables using Goebner basis

  • find the Groebner basis
  • in general NPC and EXPSPACE complete

** Using polynomial eigenvalue solver

  • hidden variable technique

Links to this note