Computing critical points with Gröbner bases: complexity bounds and
application to structured low-rank approximation.


We consider the problem of computing the critical points of a
multivariate polynomial q on an algebraic variety V. Such computations
are central in several algorithms in real algebraic geometry and in
optimization. In practice, it turns out that Gröbner bases algorithms
are efficient methods to compute these critical points which lie in
the intersection of V and of a determinantal variety defined by the
vanishing of the maximal minors of a Jacobian matrix.

Under genericity assumptions, we will discuss how the Eagon-Northcott
complex associated to this Jacobian matrix describes the underlying
combinatorial and algebraic structure of the ideal vanishing on the
critical points, which leads to complexity bounds explaining the
efficiency of Gröbner basis algorithms in this context.

Then the focus will be put on the following family of problems: for a
given linear subspace E of matrices, and a given data matrix, find the
nearest matrix (for a Euclidean distance) in E which has a given rank r. 
This nearest matrix is a critical point of the distance function
on the variety of matrices of rank r in E.  We investigate this
problem for several subspaces of matrices appearing in applications
from the viewpoint of algebraic methods and their relation to the
Euclidean distance degree.

The first part of the talk is a joint work with Jean-Charles Faugère
and Mohab Safey El Din. The second part of the talk is a joint work
with Giorgio Ottaviani and Bernd Sturmfels.