Workshop on Nonlinear Algebra

TU Berlin, March 26-27, 2020

Titles and Abstracts

Carlos Améndola - Invariant Theory and Iterative Proportional Scaling for Maximum Likelihood Estimation

We study the connection between the maximum likelihood estimate (MLE) in statistics and the null cone in geometric invariant theory. We relate the classical iterative proportional scaling (IPS) algorithm for finding the MLE to algorithms for determining null cone membership under a group action. In particular, we explore how non-existence of the MLE relates to membership to a corresponding null cone. Our two main settings are log-linear models and matrix Gaussian model. This is joint work with Kathlén Kohn, Philipp Reichenbach and Anna Seigal.

Diego Cifuentes - The geometry of SDP relaxations

Consider the problem of minimizing a polynomial function on a real algebraic variety. This is an ubiquitous problem in science and engineering, but is unfortunately NP-hard. Semidefinite programming (SDP) relaxations are a tractable method to approach it. In this talk we give an overview of SDP relaxations and discuss the underlying geometry behind them. We highlight the relationship to the algebraic degree of SDP and to the ED-degree of an algebraic variety.

Alheydis Geiger - A tropical count of binodal cubic surfaces

There are 280 binodal cubic surfaces through 17 points in general position. They can be counted using tropical geometry. After a brief introduction into tropical geometry the concept of counting surfaces through points in Mikhalkin position via floor plans will be introduced. We will see that we can recover 214 binodal surfaces with separated nodes in their tropicalizations and we will also have a short look at the complexes hiding the remaining 66 surfaces.

Kathlén Kohn - Minimal Problems in Computer Vision

A well-studied problem in computer vision is "structure from motion", where 3D structures and camera poses are reconstructed from given 2D images taken by the unknown cameras. The most classical instance is the 5-point problem: given 2 images of 5 points, the 3D coordinates of the points and the 2 camera poses can be reconstructed. In fact, given 2 generic images of 5 points, this problem has 20 solutions (i.e., 3D coordinates + 2 camera poses) over the complex numbers. Reconstruction problems which have a finite positive number of solutions given generic input images, such as the 5-point problem, are called "minimal". These are the most relevant problem instances for practical algorithms, in particular those with a small generic number of solutions. We formally define minimal problems from the point of view of algebraic geometry. Our algebraic techniques lead to a classification of all minimal problems for point-line arrangements and any number of cameras. We compute their generic number of solutions with symbolic and numerical methods. This is joint work with Timothy Duff, Anton Leykin, and Tomas Pajdla.​

Kaie Kubjas - Nonnegative rank: Rational factorizations, boundaries and semi-algebraic characterizations

Let M be a matrix with nonnegative entries. Its nonnegative rank is the smallest natural number r such that M can be written as a sum of r rank one matrices whose entries are nonnegative.
Cohen and Rothblum asked in 1993: Given a non-negative matrix with rational entries, does its non-negative rank over the rational numbers agree with its non-negative rank over the real numbers? After 23 years, two groups (Chistikov et al; Shitov) simultaneously posted papers where they construct matrices that answer this question negatively.
Matrices whose nonnegative rank over reals differs from their nonnegative rank over rationals have restricted sets of nonnegative factorizations. This means that they are on the boundary of the set of matrices of nonnegative rank at most r. These boundaries are completely understood for matrices of nonnegative rank at most three. Connection with rigidity theory allows to obtain partial understanding of boundaries for higher nonnegative rank. For nonnegative rank at most three, complete understanding of boundaries allows one to derive semi-algebraic characterizations of these sets.
Nonnegative rank can be also defined for tensors. Allman, Rhodes, Sturmfels and Zwiernik gave a semi-algebraic characterization of tensors of nonnegative rank at most two. Boundaries of this set have been recently characterized by Allman et al. Seigal and Montufar extended both of these results to 2x2x2 tensors of nonnegative rank at most 3.
This is an overview talk summarizing results from the last few years.

Fatemeh Mohammadi - Algebra and Combinatorics of Conditional Independence Models with Hidden Variables

I will start with a gentle introduction to causal inference questions on conditional independence models in statistics. In general, given a list of dependencies among random variables, it is difficult to say which constraints are implied by them. On the other hand, it is important to know what constraints on the random variables are caused by hidden variables. I will describe conditional independence (CI) models and demonstrate how the causal inference questions lead us to algebraic and combinatorial questions in the theory of matroids. I will present several combinatorial conjectures and computational challenges around this problem. For the most part, I assume only basic background from algebra and combinatorics.

Marta Panizzut - Moduli space of tropical cubic surfaces

Recent works of Ren, Sam, Shaw and Sturmfels focused on tropicalizing classical moduli spaces from their defining equations. A particularly interesting example is the moduli space of marked del Pezzo surfaces of degree three. Tropical cubic surfaces arise as fibers of the map from the Naruki fan to the Sekiguchi fan. They are fans respectively derived from the Bergam fans of type E_6 and E_7 which serve as tropical moduli spaces of six and seven points in the plane. The authors identified two generic types of such tropical cubic surfaces characterized by their structure at infinity, which is an arrangement of 27 trees with 10 leaves. In this talk we illustrate the construction highlighting the computational aspects. Moreover, we will focus on new developments on the topic such as the recent work of Cueto and Deopurkar.

Jose Israel Rodriguez - Critical points, Euler characteristics, and nearest point problems

Determining the closest point to a model (subset of Euclidean space) is an important problem in many applications in science, engineering, and statistics. One way to solve this problem is by minimizing the squared Euclidean distance function using gradient descent. However, when there are multiple local minima, there is no guarantee of convergence to the true global minimizer. An alternative method is to determine the critical points of an objective function on the model. By finding all of the critical points we are guaranteed to find a true solution to the nearest point problem.
In algebraic statistics, the models of interest are algebraic sets, i.e., solution sets to a system of multivariate polynomial equations. In this situation, the number of critical points of the squared Euclidean distance function on the model’s Zariski closure is an invariant called the Euclidean distance degree (ED degree). On the other hand, the number of critical points of the likelihood function on a model is called the Maximum Likelihood Degree (ML degree).
In this talk, I will describe a method for determining a ED degree/ML Degree by computing Euler characteristics. In particular, I will explain how a "generic function" on an algebraic variety gives rise to an Euler characteristic of an Euler obstruction function. As a first application, we prove the conjectured formula by Draisma-Horobȩt-Ottaviani-Sturmfels-Thomas for the ED degree of the affine multiview variety. As a second application, we address the problem of determining the ML Degree of the set of matrices of rank at most r, and we resolve it for r at most 2.

Benjamin Schröter - An update on the tropical Grassmannians and Dressians

Tropical Grassmannians are the moduli spaces of tropicalized linear spaces, and the tropicalizations of the ordinary Grassmannians. These tropical varieties are subsets of Dressians, the tropical prevarieties of all tropical linear spaces. Both sets are not only interesting as examples of tropical varieties and prevarieties, they are also closely related to phylogenetic trees, tropical curves of genus 0 (with marked points), (valuated) matroids, and tropical convexity. Moreover, a Dressian comes with a natural fan structure induced by a secondary fan, while a tropical Grassmannian comes with a fan structure which is induced by a Groebner fan. In this talk I will focus on these two very different fan structures, and discuss computational aspects. The results in this talk are derived from the newest example of a tropical Grassmannian, i.e., the tropical Grassmannian of 3-dimensional subspaces in 8-space.

Emre Sertöz - Developing a calculus for periods of varieties

Periods of a smooth projective variety are (often transcendental) numbers that appear as entries in a particular matrix. This matrix encodes the isomorphism between topological and algebraic realizations of cohomology groups. Periods often uniquely determine the variety, much like a defining ideal of the variety. Just like we have effective means to work with polynomial ideals to learn more about a variety, it would be desirable to develop the means to compute and manipulate periods of varieties to learn even more about that variety. We will talk about new developments in this direction and a possible future for the subject.

Ben Smith - Face posets of tropical polyhedra

Tropical polyhedra can be viewed as the logarithmic limit of families of ordinary polyhedra. As members of these families may have differing face structures, it is difficult to define a coherent notion of face for tropical polyhedra. In this talk, we offer a possible solution by introducing a notion of tropical faces for a special class of tropical polyhedra arising as tropicalisations of blocking polyhedra. We then show how this face structure may be extended to all tropical polyhedra. Furthermore, we show how this notion of tropical face is intimately related to ideas from commutative algebra and order theory. This is joint work with Georg Loho.

Bernd Sturmfels - Theta surfaces

A theta surface in affine 3-space is the zero set of a Riemann theta function in genus 3. This includes surfaces arising from special plane quartics that are singular or reducible. Lie and Poincaré showed that theta surfaces are precisely the surfaces of double translation, i.e. obtained as the Minkowski sum of two space curves in two different ways. These curves are parametrized by abelian integrals, so they are usually not algebraic. This paper offers a new view on this classical topic through the lens of computation. We present practical tools for passing between quartic curves and their theta surfaces, and we develop the numerical algebraic geometry of degenerations of theta functions.

Sascha Timme - Estimating linear covariance models with numerical nonlinear algebra

We consider the problem of maximum likelihood estimation for Gaussian models defined by linear constraints on the covariance matrix. Using numerical nonlinear algebra we examine the generic case as well as special models (e.g. Toeplitz, sparse, trees) that are of interest in statistics. In particular, we study the maximum likelihood degree and its dual analogue. We will also discuss the necessary tools and techniques from numerical nonlinear algebra to arrive at these results and how to apply them to other problems.