FB 6 Mathematik/Informatik

Institut für Mathematik

Osnabrück University navigation and search

Main content

Top content

DFG Research Training Group 2013

Opening Colloquium

DFG Research Training Group

"Combinatorial Structures in Geometry"

Friday, 1st November, 2013

10:00 a.m.-10:30 a.m. Welcome Addresses by Wolfgang Lücke, President, and Matthias Reitzner, Spokesman
10:30 a.m.-11:30 a.m. Bernd Sturmfels (University of California, Berkeley)
Maximum Likelihood for Matrices with Rank Constraints
Abstract: Maximum likelihood estimation is a fundamental computational task in statistics. We discuss this problem for manifolds of low rank matrices. These represent mixtures of independent distributions of two discrete random variables. This non-convex optimization problems lead to some beautiful geometry, topology, and combinatorics. We explain how numerical algebraic geometry is used to find the global maximum of the likelihood function, and we present a remarkable duality theorem due to Draisma and Rodriguez.
11:30 a.m.-12:00 p.m. Tea/coffee break
12:00 p.m.-01:00 p.m. Anita Schöbel (Georg-August-Universität, Göttingen)
Locating Hyperplanes and Hyperspheres: Combination of Geometric and Combinatorial Methods
Abstract: We consider the problem of approximating a set of m points in a normed space by a hyperplane or by the surface of a hypersphere. More precisely, the goal is to find a hyperplane (or hypersphere) which minimizes the sum of distances to the given points. This problem is well known in location theory where it has mostly been treated for two dimensions, in computational geometry, and it has also applications in robust statistics. In the talk we focus on the underlying structure of the problem: We present a dual interpretation of the problem and show that quasi-concavity of the objective function yields discretization results. Based on these results we develop algorithmic approaches. For the case of block norms and polyhedral gauges, we propose a linear programming formulation. We also show more specific results for the Euclidean case and for the case of the Manhattan norm.
01:00 p.m.-02:30 p.m. Lunch break
02:30 p.m.-03:30 p.m. Peter Gritzmann (Technische Universität, München)
Discrete Tomography
Abstract: Discrete tomography deals with the reconstruction of finite sets from knowledge about their interaction with certain query sets. The most prominent example is that of the reconstruction of a finite subset F of ℤd from its X-rays (i.e., line sums) in a small positive integer number m of directions. Applications of discrete tomography include quality control in semiconductor industry, image processing, scheduling, and statistica data security. After a short general introduction to the field of discrete tomography, we addresses the following questions. Does discrete tomography have the power of error correction? Can noise be compensated by taking more X-ray images, and, if so, what is the quantitative effect of taking one more X-ray? Our main theoretical result gives the first nontrivial unconditioned (and best possible) stability result. On the algorithmic side we show that while there always is a certain inherent stability, the possibility of making (worst-case) efficient use of it is rather limited. Then we deal with the discrete tomography of quasicrystals that live on finitely generated ℤ-modules in some ℝs. Focussing on aspects in which the discrete tomography of quasicrystals differs from that in the classical lattice case, we solve a basic decomposition problem for the discrete tomography of quasicystals. More generally, we study the problem of existence of pseudodiophantine solutions to certain systems of linear equations over the reals and give a complete characterization of when the index of Siegel grids is finite. The results on stability are joint work with Andreas Alpers, TU Munich, that on Siegel grids are joint work with Barbara Langfeld, U Kiel.