APPLIED ALGEBRA AND ANALYSIS ONLINE SEMINAR

October 21, 2021

An algorithm for counting realizations of minimally rigid graphs using intersection theory
Boulos El Hilany (TU Braunschweig)

The realizations of a minimally rigid graph G with respect to a general choice of edge lengths, up to rotations and translations, are determined by the solutions to a square system of quadratic equations. The number of complex solutions to this system is denoted by c(G). A Calligraph C is one resulting from removing one edge from G, followed by marking an edge and a vertex. Fixing the marked edge, the trajectory-curve T of the marked vertex is of interest in kinematics. Moreover, we can associate to C the class [C], from which one can recover the degree and bound the genus of irreducible components of T. If G can be written as a union of two calligraphs C and C', we show that c(G)=[C]·[C']. This allows one to apply a recursive procedure for computing both the numbers of realizations of minimally rigid graphs and classes of calligraphs using simpler ones. Combined with previously-known algorithms, our procedure improves the runtime significantly compared to the latest methods introduced recently by Capco, Gallet, Grasegger, Koutschan, Lubbes and Schicho. This is a joint work with Georg Grasegger and Niels Lubbes.

October 28, 2021

Lipschitz continuity of sparse super resolution and its trigonometric approximation
Mathias Hockmann (Universität Osnabrück)

Motivated by the application of neural networks in super resolution microscopy, this talk considers super resolution as the mapping of trigonometric moments of a discrete measure on [0,1)d to its support and weights. We prove that this map satisfies a local Lipschitz property where we give explicit estimates for the Lipschitz constant depending on the dimension d and the sampling effort. Moreover, this local Lipschitz estimate allows to conclude that super resolution with the Wasserstein distance as the metric on the parameter space is even globally Lipschitz continuous. Based on this, we consider simple and efficiently computable trigonometric approximations of the mapping and see that they inherit the Lipschitz property.

November 4, 2021

Faster Wasserstein distance estimation with the Sinkhorn divergence
Chizat Lénaïc (EPFL)

The squared Wasserstein distance is a natural quantity to compare probability distributions in a non-parametric setting. This quantity is usually estimated with the plug-in estimator, defined via a discrete optimal transport problem. It can be solved to ε-accuracy by adding an entropic regularization of order ε and using for instance Sinkhorn's algorithm. In this work, we propose instead to estimate it with the Sinkhorn divergence, which is also built on entropic regularization but includes debiasing terms. We show that, for smooth densities, this estimator has a comparable sample complexity but allows higher regularization levels, of order ε1/2, which leads to improved computational complexity bounds and a speedup in practice. We also propose and analyze an estimator based on Richardson extrapolation of the Sinkhorn divergence which enjoys improved statistical and computational efficiency guarantees, under a condition on the regularity of the approximation error, which is in particular satisfied for Gaussian densities. This is joint work with Pierre Roussillon, Flavien Léger, François-Xavier Vialard and Gabriel Peyré.

November 11, 2021

Distributed Learning in High Dimension
Nicole Mücke (TU Braunschweig)

While large training datasets generally offer improvement in model performance, the training process becomes computationally expensive and time consuming. Distributed learning is a common strategy to reduce the overall training time by exploiting multiple computing devices. Recently, it has been observed in the single machine setting that overparameterization is essential for benign overfitting in ridgeless regression in Hilbert spaces. We show that in this regime, data splitting has a regularizing effect, hence improving statistical performance and computational complexity at the same time.

November 18, 2021

Sensitivity of low-rank matrix approximation and recovery
Paul Breiding (MPI MiS)

We characterize the sensitivity of the output in low-rank matrix approximation with respect to perturbations in the input. The characterization is in terms of a condition number. We show that the condition number for low-rank approximation depends on the singular value gap of the input matrix. This complements prior results by Hackbusch and by Drineas and Ipsen on the sensitivity of low-rank matrix approximation. In addition, we characterize the sensitivity of approximating an incomplete matrix by a low-rank matrix. Incomplete means that some entries of the input matrix are not known or not accessible. We give an algorithm for computing the associated condition number and demonstrate in experiments how the rate of missing data affects it. This is joint work with N. Vannieuwenhoven.

November 25, 2021

Faster quantum and classical SDP approximations for quadratic binary optimization
Richard Küng (Universität Linz)

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. The class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. This is joint work with Fernando Brandao (Caltech and AWS) and Daniel Stilck Franca (QMATH, Copenhagen).

December 2, 2021

New condition-based bounds for the number of real zeros
Josué Tonelli-Cueto (Inria Paris and IMJ-PRG)

Given a real polynomial system, we will show a new family of bounds that allow us to control the number of real zeros in terms of the logarithm of the condition number. In this talk, we will discuss the ideas behind this new family of bounds and explore some of its consequences: both deterministic and probabilistic.

December 10, 2021 (Friday)

AAA in-person meeting

The event had to be canceled.

December 16, 2021

From chromatic polynomials of graphs to maximum likelihood degree, by intersection theory
Mateusz Michalek (Universität Konstanz)

Algebraic geometry has made great advances in the last two centuries. A particular role was played by enumerative geometry, where correct setting of moduli spaces found applications beyond mathematics. In my talk I would like to present a new work on applications of enumerative geometry providing a unified approach to fundamental invariants in algebraic statistics, combinatorics and topology. Achieving our results would not be possible without the fundamental work of De Concini, Huh, Laksov, Lascoux, Pragacz, Procesi and Sturmfels. The talk is based on joint works with Conner, Dinu, Manivel, Monin, Seynnaeve, Vodicka and Wisniewski.

January 13, 2022

TBA
Felix Krahmer (TU München)

to be added ...

January 20, 2022

Updating and downdating of orthogonal rational functions
Marc Van Barel (KU Leuven)

In this talk we show that rational functions with specified poles and orthogonal with respect to a discrete inner product can be efficiently and accurately computed by updating and downdating the recurrence relations for these functions by solving corresponding inverse eigenvalue problems.

January 27, 2022

TBA
Heather Harrington (University of Oxford)

to be added ...

February 3, 2022

TBA
Jonathan Hauenstein (University of Notre Dame)

to be added ...

February 10, 2022
(This talk will be at 15:30-16:30)

TBA
Mathias Drton (TU München)

to be added ...