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.
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.
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é.
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.
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.
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).
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.
AAA in-person meeting
The event had to be canceled.
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.
Unlimited Sampling from Theory to Practice
Felix Krahmer (TU München)
Shannon's sampling theorem is one of the cornerstone topics that is well understood and explored, both mathematically and algorithmically. That said, practical realization of this theorem still suffers from a severe bottleneck due to the fundamental assumption that the samples can span an arbitrary range of amplitudes. In practice, the theorem is realized using so-called analog-to-digital converters (ADCs) which clip or saturate whenever the signal amplitude exceeds the maximum recordable ADC voltage thus leading to a significant information loss. In contrast, the Unlimited Sampling Framework, an alternative paradigm for sensing and recovery recently developed by the speaker jointly with Bhandari and Raskar, called is based on the observation that when a signal is mapped to an appropriate bounded interval via a modulo operation before entering the ADC, the saturation problem no longer exists, but one rather encounters a different type of information loss due to the modulo operation. Such an alternative setup can be implemented, for example, via so-called folding or self-reset ADCs, as they have been proposed in various contexts in the circuit design literature. The key task that one needs to accomplish in order to cope with this new type of information loss is to recover a bandlimited signal from its modulo samples. In this talk we will review different approaches to this problem with a particular focus on a Fourier domain approach that is robust to non-idealities in the circuit implementation, as we observe them in experiments with a hardware prototype that we constructed for this purpose. At the mathematical core of the approach is a Prony-type method in the Fourier domain. This is joint work with Ayush Bhandari and Thomas Poskitt, Imperial College London.
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.
Algebra and topology for biological systems
Heather Harrington (University of Oxford)
Signalling pathways in molecular biology can be modelled by polynomial dynamical systems. I will present mathematical models describing two biological systems involved in development and cancer. I will overview approaches to analyse these models with data using computational algebraic geometry, differential algebra and statistics. I will also present how topological data analysis can provide additional information to distinguish wild-type and mutant molecules in one pathway. These case studies showcase how computational algebra, geometry, topology and dynamics can provide new insights to better understand model parameter values as well as biological systems with time course data, specifically how changes at the molecular scale (e.g. molecular mutations) result in kinetic differences that are observed as phenotypic changes (e.g. mutations in fruit fly wings).
Homotopy continuation for kinematic synthesis and variational inference
Jonathan Hauenstein (University of Notre Dame)
Homotopy continuation is a foundational computational approach in numerical algebraic geometry which permits the tracking of solutions to parameterized systems of nonlinear equations. In science and engineering applications, parameters such as temperature, pressure, and leg lengths naturally arise and changing such parameters can impact both the qualitative and quantitative behavior of the corresponding solutions. This talk will provide an overview of homotopy continuation along with applications in kinematic synthesis in mechanical engineering and variational inference for parameter estimation in biological models.
(This talk will be at 15:30-16:30)
Half-Trek Criterion for Identifiability of Latent Variable Models
Mathias Drton (TU München)
Linear structural equation models relate random variables of interest via a linear equation system that features stochastic noise. The 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. The details can be found in the preprint.