Seminar - Applied CATS

Tuesday 17 May 10:15
Máté Telek (University of Copenhagen)
Generalizing Descartes' rule of signs to hypersurfaces
The classical Descartes’ rule of signs provides an easily computable upper bound for the number of positive real roots of a univariate polynomial with real coefficients. Generalizations to the multivariate case have focused on systems of n polynomial equations in n variables and on bounding the number of solutions in the positive orthant. In this talk, we take a different perspective and aim to bound the number of connected components in the complement of a hypersurface in the positive orthant. We give conditions based on the geometrical configuration of the exponents and the sign of the coefficients that guarantee that the number of connected components of the complement of the hypersurface where the defining polynomial attains a negative value is at most one or two. Furthermore, we present an application for chemical reaction networks that motivated us to consider this problem. This is a joint work with Elisenda Feliu.

Tuesday 10 May 16:15 in room D31
Yulia Alexandr (UC Berkeley)
Logarithmic Voronoi cell for Gaussian models
In this talk, I will introduce the theory of logarithmic Voronoi cells for Gaussian models. I will start by defining logarithmic Voronoi cells in the discrete statistical setting and briefly discussing their properties. Then we will look at how logarithmic Voronoi cells generalize for continuous distributions. More precisely, a logarithmic Voronoi cell at a point on a Gaussian model is a convex set contained in its log-normal spectrahedron. We will see that for both directed and undirected graphical models the two sets coincide. For the latter family, I will introduce a decomposition theory of logarithmic Voronoi cells. We will also study covariance models, for which logarithmic Voronoi cells are, in general, strictly contained in log-normal spectrahedra. We will look at the bivariate correlation model in detail. This talk is based on joint work with Serkan Hosten.

Tuesday, 3 May 10:15 PhD Day Abstracts (pdf 53 kB)

Tuesday, 26 April 10:15
Fabian Roll (TU Munich) Slides
A Unified View on the Functorial Nerve Theorem and its Variations
The history of the nerve construction reaches back at least to Alexandrov (1928) and the early days of algebraic topology. Nowadays, the nerve theorem, as well as the aspect of functoriality, play a crucial role in topological data analysis. In this area, nerves are the main tool to replace a point cloud with a combinatorial model that is suitable for computations.
In this talk, I will survey certain aspects of the long history of nerves and nerve theorems, mention applications to combinatorics, and draw the connection between the nerve theorem and persistent homology.
Moreover, I will sketch a proof of the nerve theorem for covers by closed convex sets in Euclidean space that uses relatively elementary techniques. I will also set up the framework that allows us to discuss the aspect of functoriality and show two ways in which the presented nerve theorem can be turned functorial.
Finally, I will state a ``unified'' nerve theorem that establishes an equivalence between a covered space and its nerve under a variety of assumptions. If time permits, I will present some counterexamples that show the tightness of these assumptions and I will sketch the proof strategy, which uses standard techniques from modern homotopy theory such as model categories.

arxiv.org/abs/2203.03571

Tuesday, 19 April 16:15
Mauricio Velasco (Universidad de los Andes)
Harmonic hierarchies for polynomial optimization
The cone of nonnegative multivariate forms of a given degree is a convex set of remarkable beauty and usefulness.
In this talk we will discuss some recent ideas for approximating this set through polyhedra. We call the resulting approximations harmonic hierarchies since they arise naturally from harmonic analysis on spheres (or equivalently from the representation theory of SO(n)). We will describe theoretical results leading to precise estimates for the quality of these approximations and to a novel "optimization-free" algorithm for polynomial optimization. We will also show some initial computational results with our Julia implementation for harmonic hierarchies. These results are joint work with Sergio Cristancho (UniAndes).

Tuesday, 12 April 10:15
Juan M. Alonso ((BIOS) IMASL - CONICET and Universidad Nacional de San Luis)
Graphs associated to finite metric spaces
Many concrete problems are formulated in terms of a finite set of points in some $R^N$ which, via the ambient Euclidean metric, becomes a finite metric space (M,d). This situation arises, for instance, when studying the glass transition from simulations.
To obtain information from M it is not always possible to use your favorite mathematical tool directly on M. The “favorite tool” in my case is finite dimension which, although defined on finite metric spaces, is not effectively computable when M is large and unstructured. In such cases, a useful alternative is to associate a graph to M, and do mathematics directly on the graph, rather than on the space. One should think of this graph as an approximation to M.
Among the many graphs that can be associated to M, I first considered MC = MC(M), the Minimum Connected graph, a version -adapted to our situation- of the Vietoris complex of a metric space. Unfortunately MC is usually a rather dense graph. I then introduce CS = CS(M), the Connected Sparse graph, a streamlined version of MC. CS encodes the local information of M; in fact, it is almost a definition of what local structure of M means.
Despite its name, CS can be dense, even a complete graph. However, in our application to glass, we computed CS for more than 700 spaces with about 2200 points each. All of them turned out to be trees.

Tuesday, 05 April 10:15
Ruibo Tu (PhD student; Division of Robotics, Perception and Learning; KTH)
Optimal transport for causal discovery
Causal discovery aims at finding causal relationships purely from observational data.
Traditional methods, such as the PC algorithm, recover an equivalence class of the underlying
causal structures under the causal Markov condition, the faithfulness assumption, etc. To
further identify the unique causal structure, the functional causal model-based methods are
proposed; however, the model assumptions are restrictive, and their performance is sensitive
to the model assumptions, which makes it difficult to use in practice.
dynamical system view of FCMs will be introduced by leveraging the connection between FCMs
and optimal transport. It provides a new dimension for describing static causal discovery tasks
while enjoying more freedom for modeling the quantitative causal influences. Hopefully, in the
future, the assumptions of FCMs can be further relaxed.
For simplicity and clarity, we will focus on the FCMs in the bivariate case. With the light of the
new view, we find that additive noise models correspond to volume-preserving pressureless
flows. Consequently, based on their velocity field divergence, we introduce a criterion to
determine the causal relationship in the bivariate case. With this criterion, an optimal transport-
based algorithm is proposed, which is robust to the model assumptions.

Tuesday, 29 March 10:15
Wojciech Chachólski (KTH)
Homological algebra and persistence
I will explain how to use homological algebra to extract interesting invariants of various objects. I will take an opportunity to give an introduction to homological algebra techniques to a more general audience.

Tuesday, 22 March 16:15
Margaret Regan (Duke University)
A complete error analysis on solving an overdetermined system in computer vision using linear algebra
Many problems in computer vision are represented using a parametrized overdetermined system of polynomials which must be solved quickly and efficiently. Classical methods for solving these systems involve specialized solvers based on Groebner basis techniques or utilize randomization in order to create well-constrained systems for numerical techniques. We propose new methods in numerical linear algebra for solving such overdetermined polynomial systems and provide a complete error analysis showing that the numerical approach is stable. Examples will be provided to show the efficacy of the method and how the error in the data affects the error in the solution. This is joint work with Jonathan Hauenstein.

Tuesday, 15 March 10:15
Chiara Meroni (MPI-MiS Leipzig)
Polytopes and their intersection buddies
Intersection bodies are a popular construction in convex geometry. We will analyze some of their interesting features and then focus on the intersection bodies of polyotopes. They are always semialgebraic sets and are naturally related to zonotopes, which somehow describe their boundary structure. We will explore this connection via some examples and explain the ideas behind the main results. This is based on a joint work with Katalin Berlow, Marie-Charlotte Brandenburg and Isabelle Shankar. Slides (pdf 2.0 MB)

Reference:
Katalin Berlow, Marie-Charlotte Brandenburg, Chiara Meroni, and Isabelle Shankar. Intersection bodies of polytopes. Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry, January 2022. https://arxiv.org/abs/2110.05996

Tuesday, 08 March 10:15
Dino Sejdinovic (University of Oxford)
Recent Developments at the Interface Between Kernel Embeddings and Gaussian Processes
Reproducing kernel Hilbert spaces (RKHS) provide a powerful framework, termed kernel mean embeddings, for representing probability distributions, enabling nonparametric statistical inference in a variety of applications.
I will give an overview of this framework and present some of its recent developments which combine RKHS formalism with Gaussian process modelling.
Some recent applications include causal data fusion, where data of different quality needs to be combined in order to estimate the average treatment effect, as well as statistical downscaling using potentially unmatched
multi-resolution data.
References:
S. L. Chau, S. Bouabid, and D. Sejdinovic, Deconditional Downscaling with Gaussian Processes, in Advances in Neural Information Processing Systems (NeurIPS), 2021. arxiv.org/pdf/2105.12909.pdf
S. L. Chau, J.-F. Ton, J. Gonzalez, Y. W. Teh, and D. Sejdinovic, BayesIMP: Uncertainty Quantification for Causal Data Fusion, in Advances in Neural Information Processing Systems (NeurIPS), 2021. arxiv.org/pdf/2106.03477.pdf

Tuesday, 01 March 16:15
Matthew Kahle (Ohio State University)
Configuration spaces of particles and phase transitions
Configuration spaces of points in Euclidean space or on a manifold are well studied in algebraic topology. But what if the points have some positive thickness? This is a natural setting from the point of view of physics, since this the energy landscape of a hard-spheres system. Such systems are observed experimentally to go through phase transitions, but little is known mathematically.

In this talk, I will focus on two special cases where we have started to learn some things about the homology: (1) hard disks in an infinite strip, and (2) hard squares in a square or rectangle. We will discuss some theorems and conjectures, and also some computational results. We suggest definitions for "homological solid, liquid, and gas" regimes based on what we have learned so far. 

 This is joint work with Hannah Alpert, Ulrich Bauer, Robert MacPherson, and Kelly Spendlove.

Tuesday, 22 February, 10:15
Eliana Duarte (Centro de Matemática Universidade do Porto)
Representation of Context-Specific Causal models
I this talk I will introduce a class of discrete statistical models to represent context-specific conditional independence relations for discrete data. These models can also be represented by sequences of context-DAGs(directed acyclic graphs). We prove that two of these models are statistically equivalent if and only their contexts are equal and the context DAGs have the same skeleton and v-structures. This is a generalization of the Verma and Pearl criterion for equivalence for DAGs. This is joint work with Liam Solus. A video abstract is available at https://youtu.be/CccVNRFmR1I .

Tuesday, 15 February, 10:15
Maria Dostert (KTH)
Learning polytopes with fixed facet directions
In this talk we consider the task of reconstructing polytopes with fixed facet
directions from finitely many support function evaluations. We show that for
fixed simplicial normal fan the least-squares estimate is given by a convex
quadratic program. We study the geometry of the solution set and give a
combinatorial characterization for the uniqueness of the reconstruction in this
case. We provide an algorithm that, under mild assumptions, converges to
the unknown input shape as the number of noisy support function evaluations
increases. We also discuss limitations of our results if the restriction on the
normal fan is removed. This is joint work with Katharina Jochemko. Slides (pdf 3.9 MB)

Tuesday, 08 February, 10:15
Jane Ivy Coons (University of Oxford)
Symmetrically Colored Gaussian Graphical Models with Toric Vanishing Ideals 
Gaussian graphical models are multivariate Gaussian statistical models in which a graph encodes conditional independence relations among the
random variables. Adding colors to this graph allows us to describe situations where some entries in the concentration matrices in the model are assumed to
be equal. In this talk, we focus on RCOP models, in which this coloring is obtained from the orbits of a subgroup of the automorphism group of the
underlying graph. We show that when the underlying block graph is a one-clique-sum of complete graphs, the Zariski closure of the set of concentration
matrices of an RCOP model on this graph is a toric variety. We also give a Markov basis for the vanishing ideal of this variety in these cases.

Tuesday, 01 February, 10:15
Cordian Riener (UiT - The Arctic University of Norway)
#P-hardness of matrix immanants on restricted matrices
The determinant is a function from $n\times n$ matrices one encounters in linear algebra. Permanents are less known and are obtained by neglecting the \emph{signum} before each term of the determinant. The sharp difference of computational complexity of these two seemingly similar functions has been shown by Valiant in 1979. Immanants are matrix functions that generalise both determinants and permanents: They are obtained by replacing the signum with another character of the symmetric group. Immanents constitute therefore a family of matrix functions bridging from the determinant, which is obtained by the sign character and which can be evaluated in polynomial time to the #P hard permanent, which is obtained through the trivial character.
  The question, where on the way between the determinant and the permanent “easy” turns into “hard” has been initiated by Hartmann in the 1980 and improved by Barvinok and Bürgisser. Recently, Curticapean has completed this picture by providing a complete complete dichotomy result. In this talk we are going to examine what can be said if one restricts to the class of 0-1 matrices. In this context we show #P hardness for a large class of immanents. In particular, we characterise a class of partitions $\lambda$ such that it is #P hard to compute the $\lambda$-immanent of of adjacency matrices of edge-weighted, planar, directed graphs.
(This is joint work with Istvan Miklos)

Tuesday, 25 January, 10:15
Sara Magliacane (University of Amsterdam, INDE lab)
Causality-inspired ML: what can causality do for ML? The domain adaptation case.
Applying machine learning to real-world cases often requires methods that are trustworthy and robust w.r.t. heterogeneity, missing not at random or corrupt data, selection bias, non i.i.d. data etc. and that can generalize across different domains. Moreover, many tasks are inherently trying to answer causal questions and gather actionable insights, a task for which correlations are usually not enough. Several of these issues are addressed in the rich causal inference literature. On the other hand, often classical causal inference methods require either a complete knowledge of a causal graph or enough experimental data (interventions) to estimate it accurately.

Recently, a new line of research has focused on causality-inspired machine learning, i.e. on the application ideas from causal inference to machine learning methods without necessarily knowing or even trying to estimate the complete causal graph. In this talk, I will present an example of this line of research in the unsupervised domain adaptation case, in which we have labelled data in a set of source domains and unlabelled data in a target domain ("zero-shot"), for which we want to predict the labels. In particular, given certain assumptions, our approach is able to select a set of provably "stable" features (a separating set), for which the generalization error can be bound, even in case of arbitrarily large distribution shifts. As opposed to other works, it also exploits the information in the unlabelled target data, allowing for some unseen shifts w.r.t. to the source domains. While using ideas from causal inference, our method never aims at reconstructing the causal graph or even the Markov equivalence class, showing that causal inference ideas can help machine learning even in this more relaxed setting.

arxiv.org/abs/1611.10351
arxiv.org/abs/1707.06422

Tuesday, 18 January, 10:15
Barbara Mahler (KTH)
Contagion Dynamics for Manifold Learning
Contagion maps exploit activation times in threshold contagions to assign vectors in high-dimensional Euclidean space to the nodes of a network. A point cloud that is the image of a contagion map reflects both the structure underlying the network and the spreading behaviour of the contagion on it. Intuitively, such a point cloud exhibits features of the network's underlying structure if the contagion spreads along that structure, an observation which suggests contagion maps as a viable manifold-learning technique. In this talk, I will present how contagion maps and variants thereof perform as a manifold-learning tool on a number of different synthetic and real-world data sets, and compare their performance to that of Isomap, one of the most well-known manifold-learning algorithms. I will show that, under certain conditions, contagion maps are able to reliably detect underlying manifold structure in noisy data, while Isomap fails due to noise-induced error.

Tuesday, 07 December, 10:15
Pratik Misra (KTH)
Directed Gaussian graphical models with toric vanishing ideal
Directed Gaussian graphical models are statistical models that use a directed acyclic graph (DAG) to represent the conditional independence structures between a set of jointly random variables. The study of generators of the vanishing ideal of a DAG is an important problem for constraint based inference for inferring the structure of the underlying graph from data. In this talk, I will make an attempt to characterize the DAGs whose vanishing ideals are toric. In particular, I will give some combinatorial criteria to construct such DAGs from smaller DAGs which have toric vanishing ideals. In the end, for DAGs having toric vanishing ideal, I will present some results about the generating sets of those ideals. Slides (pdf 335 kB)

Tuesday, 30 November, 16:15
Anne Shiu (Texas A&M)
Identifiability of linear compartmental models 
This talk focuses on the question of how identifiability of a mathematical model, that is, whether parameters can be recovered from data, is related to identifiability of its submodels. We look specifically at linear compartmental models -- which arise in many applications including epidemiology and pharmacokinetics -- and investigate whether identifiability is preserved after adding or removing parts of the model. In particular, we examine whether identifiability is preserved when an input, output, edge, or leak is added or deleted. Our results harness standard differential algebraic techniques, so that the question of whether a model is (generically, locally) identifiable becomes equivalent to asking whether the Jacobian matrix of a certain coefficient map, arising from input-output equations, is generically full rank. Along the way, we discover a new combinatorial formula for these input-output equations, and also pose several conjectures. Slides (pdf 4.7 MB)

Tuesday, 23 November, 10:15
Michael Joswig (TU Berlin)
Tropical bisectors and Voronoi diagrams  
We consider norms in real vector spaces where the unit ball is an arbitrary convex polytope, possibly centrally symmetric. In contrast with the Euclidean norm, the topological shape of bisectors may be complicated. Our first main result is a formula for the Betti numbers of bisectors of three points in sufficiently general position. Specializing our results to the tropical polyhedral norm then yields structural results and algorithms for tropical Voronoi diagrams. The tropical distance function plays a key role in current applications of tropical geometry. Joint work with Francisco Criado and Francisco Santos. Slides (pdf 217 kB)

Tuesday, 16 November, 16:15
Bryon Aragam (University of Chicago)
New approaches to learning nonparametric (latent) causal graphical models
Interpretability and causality have been acknowledged as key ingredients to the success and evolution of modern machine learning systems. Graphical models, and more specifically directed acyclic graphs (DAGs, also known as Bayesian networks), are an established tool for learning and representing interpretable causal models. Unfortunately, estimating the structure of DAGs from data is a notoriously difficult problem, coming with a host of identifiability issues. We will discuss our recent work towards overcoming these challenges in distribution-free and nonparametric models. Starting with the fully observed case, we will discuss how known identifiability results in the linear Gaussian case can be generalized to nonparametric models. We will then discuss more difficult problems involving latent variables, and show how to identify latent causal graphs without linear or parametric assumptions. In both cases, the theory leads to efficient algorithms that are easily implemented in practice.

Tuesday, 9 November, 10:15
Anna-Laura Sattelberger (MPI-MiS Leipzig)
Algebraic Aspects of Multiparameter-TDA 
Topological data analysis uses persistent homology as a main tool to investigate data. In the one-parameter case, persistence modules naturally are graded modules over the univariate polynomial ring and hence perfectly understood from an algebraic point of view. One associates the so-called barcode, from which one reads topological features of the data. Generalizing persistent homology to a multivariate setting allows for the extraction of finer information of the data. Its algebraic properties are more subtle. In this talk, I give insights into an ongoing project with René Corbet and Wojciech Chachólski in which we study multipersistence modules. We introduce the shift-dimension. This is a new, stable invariant of multipersistence modules obtained as the hierarchical stabilization of a classical invariant. Slides

Tuesday, 2 November, 10:15
Tim Römer (Osnabrück University)
Symmetries and local-global principles in discrete geometry
We consider cones and monoids in infinite dimensional spaces which are invariant under actions of symmetric groups. A key idea is to study these objects via associated symmetric chains of cones/monoids in finite dimensional spaces and to formulate related local-global principles. In this talk we discuss recent results and open questions on these topics. Slides (pdf 153 kB)

Tuesday, 26 October, 10:15
Yue Ren (Durham University)
Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums
We present results on the number of linear regions of the functions that can be represented by artificial feedforward neural networks with maxout units. A rank-k maxout unit is a function computing the maximum of k linear functions. For networks with a single layer of maxout units, the linear regions correspond to the regions of an arrangement of tropical hypersurfaces and to the (upper) vertices of a Minkowski sum of polytopes. This is joint work with Guido Montufar and Leon Zhang. Slides (pdf 5.6 MB)

Tuesday, 12 October, 10:15
Henri Riihimäki (KTH)
Excursions into directed networks: combinatorics, algebra, and topology with machine learning
I will describe three recent works in the context of directed graphs/networks. The motivation and applications stem from brain networks of neurons and this perspective is interleaved in the talk. The three works I will describe are: 1) Machine learning pipeline for binary dynamics on a network, 2) New notion of a simplicial connectivity for directed graphs which extends Q-analysis of Atkin, and 3) How simplicial connectivities enable higher Hochschild homologies of directed graphs, going beyond degree 1 of the path algebra.

Tuesday, 05 October, 16:15
Anna Seigal (Mathematical Insitute of Oxford)
Groups and symmetries in Gaussian graphical models
We can use groups and symmetries to define new statistical models, and to investigate them. In this talk, I will discuss two families of multivariate Gaussian models: 1. RDAG models: graphical models on directed graphs with coloured vertices and edges, 2. Gaussian group models: multivariate Gaussian models that are parametrised by a group. I will focus on maximum likelihood estimation, an optimisation problem to obtain parameters in the model that best fit observed data. For RDAG models and Gaussian group models, the existence of the maximum likelihood estimate relates to linear algebra conditions and to stability notions from invariant theory. This talk is based on joint work with Carlos Améndola, Kathlén Kohn, Visu Makam, and Philipp Reichenbach. Slides (pdf 1.7 MB)

Tuesday, 28 September, 10:15
Jan Kronqvist (KTH)
Mixed-integer optimization: algorithms and strong relaxations
The presentation focuses on how to solve optimization problems containing both continuous and integer variables. The integer restrictions can originate from disjunctions, logical relations, or general integer properties of some variables. Some algorithms for solving so-called convex MINLP problems are described in the presentation, and we briefly analyze some of their properties. In the presentation, we will go through some techniques for generating tight polyhedral outer approximations of sets defined by a convex set intersected by an integer lattice. A new approach for modeling disjunctive terms is briefly presented along with an application in robust verification of ReLU-based neural networks. The presentation is intended to give a brief overview of several topics in mixed-integer optimization and some of the presenter’s research interests.

Tuesday, 21 September, 10:15
Alex Markham (KTH)
A Causal Graph Kernel Embedding via Distance Covariance
We use the distance covariance, a nonlinear measure of dependence introduced by Székely et al. 2007, to define a new kernel capable of measuring the similarity between the generating causal structures underlying different samples. Our kernel can readily be used with existing machine learning methods, allowing them to incorporate causal information to solve a wide variety of tasks (e.g., clustering with kernel k-means, classification with kernel support vector machines, or dimensionality reduction/data visualization with kernel principal component analysis). In this talk, we focus on the theoretical aspects of the kernel, namely on (i) how equivalence classes of ancestral graphs are embedded into a kernel space defined by the distance covariance and (ii) how this facilitates the isometry of distances between sample points and distances between their generating causal models. Slides (pdf 5.4 MB)

Tuesday, 14 September, 10:15
Yasuaki Hiraoka (Kyoto University, RIKEN)
On characterizing rare events in persistent homology
Indecomposables obtained through decompositions of persistent homology are regarded as topological summary of real data. However, as is well known, there exist pathologically complicated indecomposables in multi-parameter persistent homology in purely algebraic setting, and this fact makes it difficult to build mathematical theory on that setting. Our fundamental question is, how much should we care about such complicated indecomposables in the real data, and what is a suitable framework to study this question? In this talk, after explaining motivations from materials science, we will show several ongoing mathematical results, especially, (1) large deviation principle on 1 parameter persistent homology, and (2) law of large numbers on multi-parameter persistent homology. Then we will discuss how these two results (partially) answer to the original question. Slides

Tuesday, 7 September, 10:15
Isabelle Shankar (MPI Leipzig)
Symmetry Adapted Gram Spectrahedra
Sum of squares (SOS) relaxations are often used to certify nonnegativity of polynomials and are equivalent to solving a semidefinite program (SDP). The feasible region of the SDP for a given polynomial is the Gram Spectrahedron. For symmetric polynomials, there are reductions to the problem size that can be done using tools from representation theory. In joint work with Serkan Hosten and Alexander Heaton, we investigate the geometric structure of the spectrahedra that arise in the study of symmetric SOS polynomials, the Symmetry Adapted PSD cone and the Symmetry Adapted Gram Spectrahedron. Slides (pdf 736 kB)

Tuesday, 31 August, 10:15
Gennadiy Averkov (Brandenburg University of Technology)
Possibilities and limitations of semidefinite approaches to polynomial optimization
This talk is about application of semidefinite lifts to solving polynomial optimization problems. Such lifts can be used to solve non-convex polynomial optimization problems globally by reformulating them as semidefinite problems. However, the size of lifted semidefinite formulations is necessarily large in general because of an obstruction of a combinatorial nature which is expressed in terms of the facial structure of the sum-of-square cones. Slides (pdf 418 kB) Sage_example (pdf 80 kB)

Tuesday, 15 June, 11:15
Adrian Becedas
Voronoi Cells of Varieties with respect to Wasserstein Distances
(master's thesis presentation)
Voronoi diagrams are partitions of a metric space into Voronoi cells according
to distance from points on some set w.r.t. some distance. In this thesis we
examine Voronoi diagrams of manifolds and varieties w.r.t. the Wasserstein
distance from probability theory. We give some upper and lower bounds on
the dimension of Voronoi cells based on the geometry of the manifolds and
Wasserstein distance balls. We provide an upper bound on the number of full-
dimensional Voronoi cells of algebraic varieties and show examples of the
bound being tight.

Tuesday, 1 June, 11:15
Georgios-Nikolaos Karelas
Interventions for Identifying Context-Specific Causal Structures
(master's thesis presentation)
The problem of causal discovery is to learn the true causal relations among a system of random variables based on the available data. Learning the true causal structure of p variables can sometimes be difficult, but it is crucial in many fields of science, such as biology, sociology and artificial intelligence. Classically, it is assumed that the true causal relations are completely encoded via a directed acyclic graph (DAG), and there are numerous algorithms for estimating a DAG representative of a causal system from data. Assuming it is feasible, the most effective way of learning the true causal structure is through interventional experiments. Some previous work was made by Eberhardt et al. who identified the sufficient and in the worst case necessary number of interventions needed to learn a DAG, and then studied this problem from a game theoretic perspective, providing an upper bound on the expected number of experiments needed to identify the causal DAG. Here, we consider more general causal models, the CStrees, which allow for the true causal relations to be context-specific. We extend the results of Eberhardt to the family of CStrees by finding the sufficient and in the worst case necessary number of experiments the Scientist must perform in order to discover the true CStree among p variables. We generalize the game theoretic approach presented in Eberhardt's paper, to the CStrees with a specified causal ordering. We also give a geometric description of context-specific hard interventions in CStrees, through a bijection between the stages of the CStree and the faces of a polytope.

Tuesday, 25 May, 11:15
James Cussens (University of Bristol)
Branch-price-and-cut for Bayesian network structure learning
A Bayesian network structure is an acyclic directed graph
(DAG) which encodes conditional independence relations between random
variables in a joint distribution. One option for learning such a DAG from data
is to encode the graph learning problem as an integer linear program
(ILP) and send the problem to an ILP solver to solve. Unfortunately,
the number of ILP variables required to represent the problem grows
exponentially with the number of random variables. In this talk I will
report on ongoing work to get round this problem. The key idea is to
add only those ILP variables which are 'necessary' into the ILP during the course of solving the ILP, a
well-known ILP technique called 'pricing'. The talk will not assume
prior knowledge of Bayesian network structure learning or integer
linear programming.

Tuesday, 4 May, 11:15
Pierre Nyquist
A series of mini-talks on large deviations, stochastic simulation and their roles in the mathematics of data and AI
This will not be a traditional talk where I start with a well-defined research question and end with some kind of answer. Instead, it will be series of “the first 10–15 minutes” of several talks on large deviations and stochastic simulation. These are topics that are ubiquitous in a variety of areas within probability and statistics, or even more broadly in applied mathematics, but have yet to be used extensively in the area of data science. I will start with a brief introduction to the theory of large deviations, one of the cornerstones of modern probability, and then discuss problems involving e.g. gradient flows for interacting particle systems and Markov chain Monte Carlo methods for sampling from complex distributions, and how these link to important questions in data science. If time permits I will end the talk with an outline of some ongoing and future work on the mathematical foundation of data science. As we go along, I will refer back to previous talks in the seminar series to highlight how the topics I discuss have already come up in different contexts. No previous knowledge of any of the topics mentioned is required. SlidesPart1 (pdf 4.7 MB)   SlidesPart2 (pdf 2.2 MB)   SlidesPart3 (pdf 7.8 MB)

Tuesday, 27 April, 11:15
Martina Scolamerio
Extracting persistence features with hierarchical stabilisation.
It is often complicated to understand complex correlation patterns between multiple measurements on a dataset. In multi-parameter persistence we represent them through algebraic objects called persistence modules. I will present the hierarchical stabilisation framework which can be used to produce stable invariants for persistence modules. A fundamental property of such invariants is that they depend on metrics to compare persistence modules. I will then focus on one invariant, obtained via hierarchical stabilisation, called the stable rank. After explaining challenges associated to the computation of the stable rank, in the multi-parameter case, I will showcase its use for one-parameter persistence. In particular I will illustrate how the associated kernel can be used on artificial and real-world datasets and show that by varying the metric we can improve accuracy in classification tasks.
This work is in collaboration with the TDA group at KTH.

Tuesday, 20 April, 11:15
Bernd Sturmfels (UC Berkeley / MPI MiS Leipzig / TU Berlin / Leipzig University)
Linear PDE with Constant Coefficients
We discuss algebraic methods for solving systems of homogeneous linear partial differential equations with constant coefficients. The setting is the Fundamental Principle established by Ehrenpreis and Palamodov in the 1960’s. Our approach rests on recent advances in commutative algebra, and it offers new vistas on schemes and coherent sheaves in computational algebraic geometry. Slides, incl. homework (pdf 1.2 MB)

Tuesday, 13 April, 11:15
Vidit Nanda (University of Oxford)
Links, paths and intersections
Links of strata in singular spaces are fundamental invariants which govern the topology of small neighbourhoods around points in those strata. This talk will focus on inferring links of strata from incomplete information in two completely different contexts. In each case, there are exciting consequences of learning the topology of such links. No prior knowledge of stratification theory will be assumed!

Tuesday, 6 April, 11:15
Andrea Guidolin
Topological analysis of spike train data
The methods of topological data analysis have found in neuroscience a particularly fertile field of application. Their ability to capture and quantify information about shape and connections makes them relevant to study, for example, the geometry and topology of spaces of neural representations of stimuli. I will describe some successful topological methods for the analysis of neural data, focusing on the information they can extract from spike train data, i.e. lists of firing times of different neurons. As a concrete example, I will present results on the spaces of neural responses elicited by particular visual stimuli.

Tuesday, 30 March, 11:15
Elizabeth Gross (University of Hawaiʻi at Mānoa)
Mixed volumes of steady-state systems
The steady-state degree of a chemical reaction network is the number of complex solutions to the steady-state system for generic parameters. In general, the steady-state degree may be difficult to compute, but it can be bounded above by the mixed volume of the system. In this presentation, using tools from combinatorial polyhedral geometry, we compute the mixed volume for three infinite families of networks, each generated by joining smaller networks to create larger ones. Each of these examples illustrate a different relationship between the steady-state degree and the mixed volume of the steady-state system. This is joint work with Cvetelina Hill.

Tuesday, 23 March, 16:15
Peter Bubenik (University of Florida)
Summaries and Distances for Topological Data Analysis 
Topological data analysis starts with encoding data as a diagram of topological spaces. To this diagram we apply standard topological, algebraic, and combinatorial tools to produce a summary of our data. Next, we would like to be able perform a quantitative analysis. I will show how a family of distances, called Wasserstein distances, arise in a natural way, and how an extension of these ideas produces a graded version of this summary and also a summary for which we have not only distances but also angles (in fact, a Hilbert space) allowing us to apply statistics and machine learning. Key mathematical ingredients will include optimal transport, Mobius inversion, and Morse theory.

Tuesday, 16 March, 11:15
Carlos Améndola (TU Munich / Ulm University)
Likelihood Geometry of Correlation Models
Correlation matrices are standardized covariance matrices. They form an affine space of symmetric matrices defined by setting the diagonal entries to one. In this talk we will consider the fascinating geometry of maximum likelihood estimation for this model and linear submodels that encode additional symmetries. We also consider the problem of minimizing two closely related functions of the covariance matrix, the Stein's loss and the symmetrized Stein's loss, which lead naturally to the algebraic statistical concepts of dual ML degree and SSL degree. I will also present exciting open problems in this direction. This is joint work with Piotr Zwiernik.

Tuesday, 9 March, 11:15
Aida Maraj (MPI MiS Leipzig)
Asymptotic Behaviors of Hierarchical Models
A hierarchical model is realizable by a simplicial complex that describes the dependency relationships among random variables and the number of states for each random variable. Diaconis and Sturmfels have constructed toric ideals that produce Markov bases for these models. This talk concerns quantitative properties for families of ideals arising from hierarchical models with the same dependency relations and varying number of states. We introduce and study invariant filtrations of such ideals related by an action of the symmetric group, and their equivariant Hilbert series. Conditions that guarantee this multivariate series is a rational function will be presented. The key is to construct finite automata that recognize languages corresponding to invariant filtrations. Lastly, we show that one can similarly prove the rationality of an equivariant Hilbert series for some filtrations of algebras. This is joint work with Uwe Nagel.

Tuesday, 2 March, 11:15
Mathias Drton (TU Munich)
Parameter Identification in Linear Causal Models with Latent Variables
Linear causal models relate random variables of interest via a linear equation system that features stochastic noise. These models, also known as structural equation models, are naturally represented by directed graphs whose edges indicate non-zero coefficients in the linear equations. In this talk I will report on progress on combinatorial conditions for parameter identifiability in models with latent (i.e., unobserved) variables. Identifiability holds if the coefficients associated with the edges of the graph can be uniquely recovered from the covariance matrix they define.

Tuesday, 23 February, 11:15
Beatriz Pascual Escudero (Universidad Carlos III de Madrid)
Using Algebraic Geometry to detect robustness in Reaction Networks
An interesting feature of some biological systems is their capacity to preserve certain features against changes in the environmental conditions. In particular, we are concerned with the preservation of the concentration of specific species interacting in a system, motivated by examples in Reaction Networks: a biological system has absolute concentration robustness (ACR) for some molecular species if the concentration of this species does not vary among the different equilibria that the network admits. In particular, this concentration is independent of the initial conditions. While some classes of networks with ACR have been described, as well as some techniques to check ACR for a given network, finding networks with this property is a difficult task in general.
Motivated by this problem, we will explore local and global notions of robustness on the set of (real positive) solutions of a system of polynomial equations. The goal is to provide a practical test on necessary conditions for ACR, using algebraic-geometric techniques. This is based on joint work with E. Feliu.

Tuesday, 16 February, 11:15
Rickard Brüel Gabrielsson (MIT)
Topology and Machine Learning
We will talk about connections between topology and machine learning. Statistics and local geometry has for a long time served as the underpinning of machine learning, but recent developments allow us to incorporate global geometry and topology with great results. First, topological features such as persistent homology and clustering methods can help us understand what neural networks learn and construct topology inspired learning theory. Next, many of these features are differentiable which allows us to create a general purpose machine learning layer that allows anyone to easily incorporate topology into any machine learning pipeline. Lastly, we will talk about universal function approximation on graphs and the promise of unsupervised learning and pre-training.

Tuesday, 9 February, 15:45
Rehka Thomas (University of Washington)
Multiview Chirality, Two Cameras and a Cubic Surface
The set of images captured by an arrangement of pinhole cameras is usually modeled by an algebraic variety called the multiview variety. The true set is in fact a semialgebraic subset of this variety, arising from the physical restriction that cameras can only image points in front of them. I will discuss this set for multiple cameras. For a pair of cameras, the minimal problem in this semialgebraic setting is given by 5 point pairs, which even in general position, can fail to have a "chiral" 3-dimensional reconstruction. We will see that the combinatorics and arithmetic information of this minimal case is carried by a cubic surface with 27 real lines.
Joint work with Sameer Agarwal, Andrew Pryhuber and Rainer Sinn

Tuesday, 26 January, 11:15
Kaie Kubjas (Aalto University, Helsinki)
Uniqueness of nonnegative matrix factorizations
Nonnegative matrix factorizations are often encountered in data mining applications where they are used to explain datasets by a small number of parts. For many of these applications it is desirable that there exists a unique nonnegative matrix factorization up to trivial modifications given by scalings and permutations. This means that model parameters are uniquely identifiable from the data. Different sufficient conditions for the uniqueness of nonnegative matrix factorizations have been well studied, however, a little is known about necessary conditions. We will give so far the strongest necessary condition for the uniqueness of a nonnegative factorization. The talk is based on the joint work with Robert Krone.

Tuesday, 19 January, 11:15
Katharina Jochemko
Points, polytopes, polynomials
Ehrhart theory is concerned with the enumeration of lattice points in polytopes. Given a polytope with vertices in the integer lattice, the function counting the lattice points in its integer dilates agrees with a polynomial, the Ehrhart polynomial of the polytope. In this talk, I will give a brief overview of some of my research interests in Ehrhart theory, in particular, geometric models for enumerative problems, structural results for Ehrhart polynomials as well as ties to valuation theory. Slides (pdf 911 kB)

Tuesday, 17 November, 11:15
Kathlén Kohn
Nonlinear Algebra of Data Science and AI
Nonlinear algebra is the study of systems of multivariate polynomial equations and inequalities. At the heart of this lies algebraic geometry, but the field is driven by many other areas of mathematics such as combinatorics, convex and discrete geometry, multilinear algebra, tropical geometry, or representation theory. Systems of polynomial (in)equalities appear vastly throughout the sciences and engineering. In this talk, I will focus on applications in data science and artificial intelligence. My research focuses on uncovering geometric structures in applied problems and on finding connections between seemingly unrelated areas of mathematics or science in general. I will demonstrate this by describing the underlying (algebraic) geometry of machine learning with neural networks and of 3D reconstruction in computer vision. I will also outline surprising connections between statistics, invariant theory, geometric modeling, intersection theory, and physics. Slides (pdf 4.3 MB)

Tuesday, 10 November, 11:15
Johan Håstad
Some of my interests and (old) results
I work in complexity theory and recently I have studied efficient approximability of NP-hard optimization problems. In particular I have been interested in constraint satisfaction problems (CSPs). In a CSP you are given a large number of constraints each only depending on a constant number of variables and the goal is to find an assignment to satisfy as many constraints as possible. Central examples are Max-3Sat and sets of linear equations over a finite field where each equation only depends on three variables. I will also briefly mention some problems in post-quantum cryptography. slides (pdf 264 kB)