Monday, February 4, 2013
Freie Universität Berlin
Institut für Informatik
14195 Berlin Berlin
Lecture - 14:15
In isotonic regression, we want to approximate given sequence of numbers a1,..., an by numbers x1,x2,...,xn subject to constraints of the form x_i<=x_j, for certain pairs (i,j).
The objective is to minimize some error based on the deviations |x_i-a_i|, typically the L1, L2 or Lmax norm, possibly with weights. The simplest case is when x1,x2,...,xn is required to be an increasing sequence, but other types of orders have been considered: tree-like orders, orders given by an arbitrary directed acyclic graph, d-dimensional orders, or d-dimensional arrays.
1. I will describe the classical Pool Adjacent Violators (PAV) method, which has been extensively studied.
2. I will describe a simple dynamic programming approach for the linearly ordered case, which leads to a quite general and versatile method, also for the related bitonic regressen problem.
3. I will point out the relation to minimum-cost flows.
4. I will finally describe a randomized method for d-dimensional orders, which improves previous methods and uses less space.
It is based on a general optimization technique of Timothy Chan.
Colloquium - 16:00
A notion of relaxation for an incompatible system of linear homogeneous inequalities is introduced. We show that the minimal subset of inequalities that must be relaxed in order the system to be compatible is well defined. This result is used to show that the finest regular coarsening of a polyhedral subdivision and its regularity poset are also well defined. Some properties of these objects are derived, which confer structure on the set of non-regular subdivisions of a given point set. The class of recursively-regular subdivisions is defined. We show that given a point set, its recursively-regular subdivisions are a superset of its regular subdivisions and a subset of its visibility-acyclic subdivisions.
Joint work with Günter Rote.