Numerical condition in polynomial equation solving
Numerical computations are affected by errors (e.g., due to round-off),
hence it is important to understand the sensitivity of the results with regard to perturbations.
This can be quantified by condition numbers. This concept is well-known
in numerical linear algebra, but less so in optimization and polynomial equation solving,
even though it plays an important role not only for sensitivity analysis, but also
for designing and understanding the complexity of iterative methods.
The goal of the talk is to provide a high-level overview of this,
focussing on polynomial equation solving.
SPECTRA: solving exactly linear matrix inequalities
The set of real points such that a symmetric pencil is positive
semidefinite is a convex semi-algebraic set called spectrahedron,
described by a linear matrix inequality (LMI). After recalling the specific
geometric features of spectrahedra and their versatility in convex
algebraic geometry, we describe our Maple package SPECTRA that computes
an exact algebraic representation of at least one point in a given spectrahedron,
or decides that it is empty. In particular, our algorithm does not assume
the existence of an interior point, and the computed point minimizes
the rank of the pencil on the spectrahedron. Our experiments show
significant improvements with respect to state-of-the-art computer algebra
algorithms. This is joint work with Simone Naldi and Mohab Safey El Din.
Critical Configurations for Projective Reconstruction from Multiple Views
In this talk, a classical problem in computer vision is investigated: Given corresponding points in multiple
images, when is there a unique projective reconstruction of the 3D geometry of the scene points and the camera
positions? A set of points and cameras is said to be critical when there is more than one way of realizing the resulting
image points. For two views, it has been known for almost a century that the critical configurations consist of points
and camera lying on a ruled quadric surface. We give a classification of all possible critical configurations for any
number of points in three images, and show that in most cases, the ambiguity extends to any number of cameras.
The theoretical results are accompanied by many examples and illustrations.
Minimal Problems - What works and what does not
We will review some our recent developments in solving minimal problems in
computer vision (radial distortion with homography, rolling shutter
absolute camera pose, L2 three view triangulation) and will point to issues
that seem to be difficult for us and could motivate further development of
algebraic methods for solving computer vision problems.
Chordal structure and polynomial systems
Abstract: tba
(Radial) Multi-focal tensors:
Concept, internal constraints and geometric insight
Abstract: tba
Solving polynomial systems over the reals exactly: why and how?
Polynomial system solving appear in many problems of engineering
sciences, including computer vision. Most of the time, the end-user
expects to get some information on the real solution set of such
systems. We will explain why algebraic computation (i.e. computer
algebra) becomes an essential ingredient for solving some families of
such systems, the main geometric ideas on which these algorithms rely
and how to use them efficiently.
Photogrammetry Profiles and Classical Invariant Theory
For a fixed object, its profile is defined as the set of all possible image (from all possible camera positions). Typically, images are defined up to some equivalence (e.g. projective transformations). Therefore the profiles can naturally be embedded in quotient varieties. Tasks in photogrammetry, such as identifying an object from a fixed number of images, reduce to interpolating specific subvarities in these quotient varieties. In this talk we explain this connection with several examples (Segre cubic, Igusa quartic).
Varieties, Parameters, and Moduli
Multiview varieties, camera matrices, and various tensors play a
central role in algebraic vision. This lecture introduces these objects from
a perspective that is entirely natural to those studying algebraic geometry.
Subspace Arrangements in Vision and Learning
The problem of clustering data drawn from multiple linear subspaces can be posed as one of estimating and decomposing a subspace arrangement into its irreducible components. Over the past decade, this problem has found widespread applications in computer vision, including image and video segmentation, face and digit clustering, and hybrid system identification. This lecture will review the classical GPCA algorithm for solving this problem, which is based on estimating and factorizing multivariate homogeneous polynomials. The lecture will also present extensions to the classical GPCA algorithm that can handle data corrupted by noise and outliers by constructing a descending subspace filtration. Applications to motion segmentation will also be presented.