Kickoff Workshop for the Emmy-Noether Research Group “Numerical and Probabilistic Nonlinear Algebra”

Abstracts for the talks

Peter Bürgisser
TU Berlin
Time: Tuesday, September 21, 2021, 11:00

The Zonoid Algebra, Generalized Mixed Volumes, and Random Determinants
We show that every multilinear map between Euclidean spaces induces a unique, continuous, Minkowski multilinear map of the corresponding real cones of zonoids. Applied to the wedge product of the exterior algebra Λ(V ) of a Euclidean space V, this defines the structure of a commutative, associative, and ordered ring on the space A(V ) of virtual zonoids of Λ(V ), which we call the zonoid algebra of V. Our construction incorporates the notion of mixed volume from convex geometry via the length of zonoids (first intrinsic volume), which can be thought of as their average diameter. We also analyze a similar construction based on the complex wedge product on Cn, which naturally leads to the new notion mixed J-volume. These constructions allow to express the expected absolute determinant of random matrices in terms of zonoids.
This work prepares the ground for a probabilistic intersection theory for compact homogenous spaces. Ongoing work with Paul Breiding, Antonio Lerario and Leo Mathis.

Timo de Wolff
TU Braunschweig
Time: Monday, September 20, 2021, 13:00

An Introduction to Nonnegativity and Polynomial Optimization
In science and engineering, we regularly face polynomial optimization problems, that is: minimize a real, multivariate polynomial under polynomial constraints. Solving these problems is essentially equivalent to certifying of nonnegativity of real polynomials -- a key problem in real algebraic geometry since the 19th century. Since this is a notoriously hard to solve problem, one is interested in certificates that imply nonnegativity and are easier to check than nonnegativity itself. In particular, a polynomial is nonnegative if it is a sums of squares (SOS) of other polynomials. Being an SOS can be detected effectively via semidefinite programming (SDP) in practice.
In 2014, Iliman and I introduced a new certificate of nonnegativity based on sums of nonnegative circuit polynomials (SONC), which I have developed further since then both in theory and practice joint with different coauthors. In particular, these certificates are independent of sums of squares and can be computed via relative entropy programs.
In this talk, I will give an introduction to the world of polynomial optimization, nonnegativity, SOS, and SONC.

Samantha Fairchild
Time: Monday, September 20, 2021, 14:30

An Introduction to Counting Closed Geodesics on Translation Surfaces
A translation surface is a collection of polygons in the plane with parallel sides identified by translation to form a surface with a singular Euclidean structure. Closed geodesics on a translation surface are straight lines which start and end at a vertex of one of the polygons. Through some concrete examples we will give probabilistic results on counting closed geodesics for certain families of translation surfaces. These translation surfaces live in SL(2,R) orbit closures that are in fact algebraic varieties in the moduli space of translation surfaces, and are equipped with a natural SL(2,R) invariant probability measure.

Zakhar Kabluchko
University of Münster
Time: Tuesday, September 21, 2021, 09:30

Face Numbers of Random Polytopes and Angles of Random Simplices
Let X1,X2,,Xn be n random points drawn uniformly at random from the d-dimensional unit ball. What is the expected number of k-dimensional faces of their convex hull [X1,,Xn]? Let Y 1,,Y d+1 be d + 1 random points sampled uniformly at random on the unit sphere in d. What is the expected sum of solid angles of the simplex with vertices at Y 1,d+1? We shall review recent results on these and some other questions of stochastic geometry.

Guido Montufar
Time: Monday, September 20, 2021, 09:30

On the Expected Complexity of Maxout Networks
Learning with neural networks relies on the complexity of the representable functions, but more importantly, the particular assignment of typical parameters to functions of different complexity. Taking the number of activation regions as a complexity measure, recent works have shown that the practical complexity of deep ReLU networks is often far from the theoretical maximum. In this work we show that this phenomenon also occurs in networks with maxout (multi-argument) activation functions and when considering the decision boundaries in classification tasks. We also show that the parameter space has a multitude of full-dimensional regions with widely different complexity, and obtain nontrivial lower bounds on the expected complexity. Finally, we investigate different parameter initialization procedures and show that they can increase the speed of convergence in training. The linear regions of the functions represented by a maxout network correspond to the faces of polytopes obtained by building convex hulls and Minkowski sums of polytopes. Hence these results can be interpreted as statements about the expected number of faces of certain compositions of random polytopes.
This is joint work with Hanna Tseran

Sonja Petrovic
Illinois Institute of Technology
Time: Monday, September 20, 2021, 11:00

Sampling and Learning from Random Polynomials: Two Stories
This talk is motivated by probabilistic models of random monomial ideals that mirror and extend those from random graphs and simplicial complexes literatures. Our results provide precise probabilistic statements about various algebraic invariants of (coordinate rings of) monomial ideals: the probability distributions, expectations and thresholds for events involving monomial ideals with given Hilbert function, Krull dimension, first graded Betti numbers.
We will tackle the following related questions: What is a systematic way, in a probabilistic-model sense, to generate binomial ideals randomly? What can be (machine) learned from such data sets? How do we 'test out the waters' to see if a problem is 'learnable'? How do we generate, share, and make available large training data sets for machine learning in computational algebra?
These topics are based on joint work with various collaborators and students and form a two-step process in learning on algebraic structures.

Rainer Sinn
Universität Leipzig
Time: Monday, September 20, 2021, 16:00

Image Reconstruction and Chirality in Computer Vision
We first discuss image formation in computer vision (modelling pinhole cameras as projections in projective space) and the associated (complex) algebraic descriptions. The reverse problem is called scene reconstruction which is our second topic. Along the way, we will see real algebraic refinements of the established complex algebraic picture capturing that the constraints that images are taken of an actual three-dimensional scene in real projective space and that the scene is in front of each camera.

Max von Renesse
Universität Leipzig
Time: Tuesday, September 21, 2021, 13:00

Spectral Gap Estimates for Brownian Motion on Manifolds with Sticky Reflecting Boundary Diffusion
We review some basic concepts in the interplay of Ricci curvature and Brownian motion on Riemannian manifolds. The second part is devoted to some new results for the case of sticky reflecting boundary diffusion. Such processes interpolate between plain Neumann reflection in the interior and surface diffusion on the boundary. We present new spectral gap estimates in terms of Ricci curvature in the interior and mean curvature on the boundary. (Joint work with Victor Marx and Vitalii Konarovskyi.)


Date and Location

September 20 - 21, 2021
Max Planck Institute for Mathematics in the Sciences
Inselstr. 22
04103 Leipzig

Scientific Organizers

Paul Breiding
MPI for Mathematics in the Sciences

Administrative Contact

Saskia Gutzschebauch
MPI for Mathematics in the Sciences
Contact by Email
24.09.2021, 01:27