Web: http://www.ima.umn.edu | Email: ima-staff@ima.umn.edu | Telephone: (612) 624-6066 | Fax: (612) 626-7370
Additional newsletters available at http://www.ima.umn.edu/newsletters

IMA Newsletter #364

February 2007

2006-2007 Program

Applications of Algebraic Geometry

See http://www.ima.umn.edu/2006-2007 for a full description of the 2006-2007 program on Applications of Algebraic Geometry.

IMA in the news - Check-out the article IMA Hosts 2006 Blackwell-Tapia Conference by Barry Cipra in the January/February 2007 issue of SIAM News.

Opportunities at the IMA - If you are interested in applying for a General Membership for a period of one month to one year in residence at the IMA during the 2007-2008 thematic program: Mathematics of Molecular and Cellular Biology, please find the application for this membership at our Applications site.

New Directions Short Course: The IMA is currently accepting applications for the 2007 New Directions Short Course - Compressive Sampling and Frontiers in Signal Processing June 4 - 15, 2007, taught by Emmanuel Candes, Ron DeVore and Rich Barniuk. This exploding area of research has connections to many areas of mathematics and presents many research opportunities. No prior background in signal processing is expected. Participants will receive full travel and lodging support during the workshop. Participation is by application only. Application deadline: April 1, 2007.

IMA is seeking a new director: The IMA is looking for a new director to begin in summer 2008.

Schedule

Thursday, February 1

11:15a-12:15pReal algebraic geometry tutorial: Quotients of polynomial rings, Hermite's quadratic form and root countingKenneth R. Driessel (Iowa State University)Lind Hall 409 RAG

Friday, February 2

1:25p-2:25pIMA/MCIM Industrial problems seminar: Data fusion in a UAV surveillance systemJanet Pavelich Keel (Lockheed Martin Missiles and Space Company, Inc.)Vincent Hall 1 IPS

Tuesday, February 6

11:15a-12:15pIMA postdoc seminar: Characterization and computation of real-radical ideals using semidefinite programming techniquesPhilipp Rostalski (Eidgenössische TH Zürich-Hönggerberg)Lind 215 PS

Wednesday, February 7

11:15a-12:15pAlgebraic geometry and applications seminar: An introduction to algebraic statisticsSerkan Hosten (San Francisco State University)EE/CS 3-180 AGS

Thursday, February 8

11:15a-12:15pReal algebraic geometry tutorial: Quotients of polynomial rings, Hermite's quadratic form and root counting (continued)Kenneth R. Driessel (Iowa State University)Lind Hall 409 RAG

Tuesday, February 13

11:15a-12:15pIMA postdoc seminar: The small Chvátal rank of an integer matrixTristram Bogart (University of Washington)Lind 215 PS

Wednesday, February 14

Thursday, February 15

11:15a-12:15pReal algebraic geometry tutorial: Quotients of polynomial rings, Hermite's quadratic form and root counting (continued)Kenneth R. Driessel (Iowa State University)Lind Hall 409 RAG

Monday, February 19

All DayPresidents' Day. The IMA is open.

Tuesday, February 20

11:15a-12:15pIMA postdoc seminar: Counting rational curves in P2 using Kontsevich's formulaHannah Markwig (University of Minnesota Twin Cities)Lind 215 PS
2:30p-3:30pIMA postdoc seminar: Variational partial differential equation(PDE) models with an application to medical imagingJungha An (University of Minnesota Twin Cities)Lind Hall 409 PS

Wednesday, February 21

11:15a-12:15pAlgebraic geometry and applications seminar: Rational and algebraic invariants of a group actionEvelyne Hubert (Institut National de Recherche en Informatique Automatique (INRIA))EE/CS 3-180 AGS

Thursday, February 22

Tuesday, February 27

11:15a-12:15pIMA postdoc seminar: Counting rational curves in P2 using tropical geometryMichael Kerber (Universität Kaiserslautern)Lind 215 PS

Wednesday, February 28

11:15a-12:15pAlgebraic geometry and applications seminar: Moving frames in classical invariant theory and computer vision Peter J. Olver (University of Minnesota Twin Cities)EE/CS 3-180 AGS
Abstracts
Tristram Bogart (University of Washington) IMA postdoc seminar: The small Chvátal rank of an integer matrix
Abstract: Given an integer matrix A and an integer vector b, we define the small Chvatal rank (SCR) of the system Ax <= b to be the least number of iterations of an iterated Hilbert basis construction to obtain all facet normals of the integer hull (that is, the convex hull of the set of integer solutions. Our procedure is a variation of the Chvatal-Gomory procedure to compute integer hulls of polyhedra. The key difference is that our procedure ignores the right-hand side vector b and uses only the matrix A.

We prove that the SCR of Ax <= b is bounded above by the Chvatal rank of Ax <= b and is hence finite. To justify the adjective "small", we show that when n=2, SCR is at most one while Chvatal rank can be arbitrarily high. For a family of examples from combinatorial optimization, we prove that the SCR is one or two while the Chvatal rank is known to be roughly log(n).

We next relate SCR to the notion of supernormality of a vector configuration (specifically, the rows of A.) Supernormality is a generalization of unimodularity and we exhibit an infinite family of vector configurations arising from odd cycles that are supernormal but not unimodular. This answers a question of Hosten, Maclagan and Sturmfels.

Lastly, we provide lower bounds on SCR. We prove that when n >= 3, SCR can be arbitrarily high and exponentially large in the input size. We also prove that for polytopes contained in the d-dimensional unit cube, the SCR can be at least d/2 - o(d) which is of the same order as the known lower bounds on Chvatal rank for such systems. Our methods thus provide an alternate way to compute lower bounds on Chvatal rank.

This project is joint work with Rekha Thomas.

Kenneth R. Driessel (Iowa State University) Real algebraic geometry tutorial: Quotients of polynomial rings, Hermite's quadratic form and root counting (continued)
Abstract: I shall mainly follow the material in the section "Zero-dimensional systems" in the book by Basu, Pollack and Roy.
Stephen E. Fienberg (Carnegie-Mellon University) Algebraic geometry and applications seminar: Statistical formulation of issues associated with multi-way contingency tables and the links to algebraic geometry
Abstract: Many statistical problems arising in the context of multi-dimensional tables of non-negative counts (known as contingency tables) have natural representations in algebraic and polyhedral geometry. I will introduce some of these problems in the context of actual examples of large sparse tables and talk about how we have treated them and why. For example, our work on bounds for contingency table entries has been motivated by problems arising in the context of the protection of confidential statistical data results on decompositions related to graphical model representations have explicit algebraic geometry formulations. Similarly, results on the existence of maximum likelihood estimates for log-linear models are tied to polyhedral representations. It turns out that there are close linkages that I will describe.
Serkan Hosten (San Francisco State University) Algebraic geometry and applications seminar: An introduction to algebraic statistics
Abstract: This will be a gentle introduction to the applications of algebraic geometry to statistics. The main goal of the talk is to present statistical models, i.e. sets of probability distributions (defined parametrically most of the time), as algebraic varieties. I will give examples where defining equations of such statistical model varieties have been successfully computed: various graphical models and models for DNA sequence evolution. I will also talk about the algebraic degree of maximum likelihood estimation with old and new examples.
Evelyne Hubert (Institut National de Recherche en Informatique Automatique (INRIA)) Algebraic geometry and applications seminar: Rational and algebraic invariants of a group action
Abstract: We consider a rational group action on the affine space and propose a construction of a finite set of rational invariants and a simple algorithm to rewrite any rational invariant in terms of those generators. The construction can be extended to provide algebraic foundations to Cartan's moving frame method, as revised in [Fels & Olver 1999]. This is joint work with Irina Kogan, North Carolina State University.
Janet Pavelich Keel (Lockheed Martin Missiles and Space Company, Inc.) IMA/MCIM Industrial problems seminar: Data fusion in a UAV surveillance system
Abstract: This talk will be about a recent Lockheed Martin project, the implementation of a data fusion method in the surveillance system of an Unmanned Aerial Vehicle (UAV). In this context data fusion is the problem of sequentially estimating the state of a dynamic system - ships at sea - given a sequence of noisy and incomplete measurements from the sensor suite on the UAV: radar, an Electro-Optical/Infrared (EO/IR) camera, and an Automatic Identification System (AIS) receiver. We will present the basic algorithms used in this project, and will then discuss their limitations and possible improvements.
Michael Kerber (Universität Kaiserslautern) IMA postdoc seminar: Counting rational curves in P2 using tropical geometry
Abstract: Tropical geometry is a rapidly developing field of algebraic geometry with important applications in quite distinct areas of pure and applied mathematics. In this talk, we give a short introduction to the theory of tropical curves and discuss its applications to the enumerative geometry of plane curves, with a focus on computing the Kontsevich number Nd of rational plane curves of fixed degree d interpolating an appropriate number of given points in general position.
Hannah Markwig (University of Minnesota Twin Cities) IMA postdoc seminar: Counting rational curves in P2 using Kontsevich's formula
Abstract: The numbers Nd of rational plane curves has for a long time only been known for small d. In 1990, Kontsevich came up with a recursive formula. In this talk, we will give some basic ideas and an example how Kontsevich's formula can be derived.
Peter J. Olver (University of Minnesota Twin Cities) Algebraic geometry and applications seminar: Moving frames in classical invariant theory and computer vision
Abstract: Classical invariant theory was inspired by the basic problems of equivalence and symmetry of polynomials (or forms) under the projective group. In this talk, I will explain how a powerful new approach to the Cartan method of moving frames can be applied to classify algebraic and differential invariants for very general group actions, leading, among many other applications, to new solutions to the equivalence and symmetry problems arising in both invariant theory, differential geometry, and object recognition in computer vision.
Philipp Rostalski (Eidgenössische TH Zürich-Hönggerberg) IMA postdoc seminar: Characterization and computation of real-radical ideals using semidefinite programming techniques
Abstract: In this talk I will discuss a method (joined work with M. Laurent and J.-B. Lasserre) for computing all real points on a zero-dimensional semi-algebraic set described by polynomial equalities and inequalities as well as some "nice" polynomial generators for the corresponding vanishing ideal, namely border resp. Gröbner basis for the real radical ideal. In contrast to exact computational algebraic methods, the method we propose uses numerical linear algebra and semidefinite optimization techniques to compute approximate solutions and generator polynomials. The method is real-algebraic in nature and prevents the computation of any complex solution. The proposed methods fits well into a relatively new branch of mathematics called "Numerical Polynomial Algebra."
Visitors in Residence
Elizabeth Allman University of Alaska 1/7/2007 - 4/7/2007
Jungha An University of Minnesota Twin Cities 9/1/2005 - 8/31/2007
Douglas N. Arnold University of Minnesota Twin Cities 7/15/2001 - 8/31/2007
Donald G. Aronson University of Minnesota Twin Cities 9/1/2002 - 8/31/2007
Hélène Barcelo Arizona State University 2/3/2007 - 3/31/2007
Daniel J. Bates University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Arend Bayer University of Utah 2/19/2007 - 2/19/2007
Yermal Sujeet Bhat University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Víctor Blanco Izquierdo University of Sevilla 1/11/2007 - 4/21/2007
Cristiano Bocci Università di Milano 1/10/2007 - 3/10/2007
Tristram Bogart University of Washington 1/8/2007 - 3/25/2007
Enrico Carlini Politecnico di Torino 1/10/2007 - 2/16/2007
Ionut Ciocan-Fontanine University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Alicia Dickenstein University of Buenos Aires 2/15/2007 - 3/14/2007
Kenneth R. Driessel Iowa State University 9/1/2006 - 6/29/2007
Mathias Drton University of Chicago 1/8/2007 - 3/30/2007
Nicholas Eriksson Stanford University 2/14/2007 - 3/16/2007
Makan Fardad University of Minnesota Twin Cities 8/26/2006 - 8/13/2007
Stephen E. Fienberg Carnegie-Mellon University 1/1/2007 - 3/31/2007
Ioannis Fotiou Eidgenössische TH Zürich-Hönggerberg 1/10/2007 - 2/16/2007
Jason E. Gower University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Gloria Haro Ortega University of Minnesota Twin Cities 9/1/2005 - 8/31/2007
Milena Hering University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Patricia Hersh Indiana University 2/15/2007 - 5/15/2007
Sung-Pil Hong Seoul National University 1/16/2007 - 2/1/2007
Serkan Hosten San Francisco State University 1/2/2007 - 2/16/2007
Benjamin J. Howard University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Evelyne Hubert Institut National de Recherche en Informatique Automatique (INRIA) 9/1/2006 - 6/30/2007
Farhad Jafari University of Wyoming 9/1/2006 - 6/30/2007
Anders Nedergaard Jensen Aarhus University 9/6/2006 - 6/30/2007
Steve Kaliszewski Arizona State University 1/7/2007 - 6/30/2007
Mordechai Katzman University of Sheffield 1/10/2007 - 5/15/2007
Janet Pavelich Keel Lockheed Martin Missiles and Space Company, Inc. 2/2/2007 - 2/2/2007
Michael Kerber Universität Kaiserslautern 2/19/2007 - 5/11/2007
Song-Hwa Kwon University of Minnesota Twin Cities 8/30/2005 - 8/31/2007
Jean Bernard Lasserre Centre National de la Recherche Scientifique (CNRS) 1/7/2007 - 2/3/2007
Niels Lauritzen Aarhus University 8/28/2006 - 7/10/2007
Anton Leykin University of Minnesota Twin Cities 8/16/2006 - 8/15/2007
Hstau Liao University of Minnesota Twin Cities 9/2/2005 - 8/31/2007
Laura Lurati University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Gennady Lyubeznik University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Hannah Markwig University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Thomas Markwig Universität Kaiserslautern 9/1/2006 - 6/30/2007
Richard Moeckel University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Uwe Nagel University of Kentucky 9/1/2006 - 6/1/2007
Jiawang Nie University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Peter J. Olver University of Minnesota Twin Cities 2/28/2007 - 2/28/2007
Michael E. O'Sullivan San Diego State University 2/21/2007 - 3/24/2007
Lior Pachter University of California 2/28/2007 - 3/10/2007
Helfried Peyrl Automatic Control Laboratory 1/15/2007 - 2/3/2007
Mihai Putinar University of California 1/7/2007 - 3/24/2007
Victor Reiner University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
John A. Rhodes University of Alaska 1/7/2007 - 4/7/2007
Joel Roberts University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Daniel Robertz RWTH Aachen 2/18/2007 - 4/1/2007
Marie Rognes University of Oslo 1/10/2007 - 6/30/2007
Amos Ron University of Wisconsin 2/14/2007 - 2/14/2007
Philipp Rostalski Eidgenössische TH Zürich-Hönggerberg 1/2/2007 - 2/19/2007
Bjarke Hammersholt Roune Aarhus University 9/12/2006 - 6/30/2007
Arnd Scheel University of Minnesota Twin Cities 7/15/2004 - 8/31/2007
Chehrzad Shakiban University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Aleksandra Slavkovic Pennsylvania State University 1/31/2007 - 3/31/2007
Frank Sottile Texas A & M University 2/26/2007 - 6/30/2007
Steven Sperber University of Minnesota Twin Cities 9/1/2006 - 6/30/2007
Andrew Stein University of Michigan 2/6/2007 - 2/8/2007
Seth Sullivant Harvard University 2/19/2007 - 3/30/2007
Rebecca Swanson Indiana University 2/22/2007 - 3/31/2007
Rekha R. Thomas University of Washington 1/1/2007 - 3/31/2007
Carl Toews University of Minnesota Twin Cities 9/1/2005 - 8/31/2007
John Voight University of Minnesota Twin Cities 8/15/2006 - 8/31/2007
Josephine Yu University of California 1/9/2007 - 6/30/2007
Hongchao Zhang University of Minnesota Twin Cities 9/1/2006 - 8/31/2007
Lihong Zhi Chinese Academy of Sciences 1/11/2007 - 3/4/2007
Yi Zhou Carnegie-Mellon University 2/28/2007 - 3/16/2007
Legend: Postdoc or Industrial Postdoc Long-term Visitor

IMA Affiliates:
3M, Boeing, Carnegie-Mellon University, Corning, ExxonMobil, Ford, General Electric, General Motors, Georgia Institute of Technology, Honeywell, IBM, Indiana University, Iowa State University, Johnson & Johnson, Kent State University, Lawrence Livermore National Laboratory, Lockheed Martin, Los Alamos National Laboratory, Medtronic, Michigan State University, Michigan Technological University, Mississippi State University, Motorola, Northern Illinois University, Ohio State University, Pennsylvania State University, Purdue University, Rice University, Rutgers University, Sandia National Laboratories, Schlumberger-Doll, Schlumberger-Doll Research, Seoul National University, Siemens, Telcordia, Texas A & M University, University of Chicago, University of Cincinnati, University of Delaware, University of Houston, University of Illinois at Urbana-Champaign, University of Iowa, University of Kentucky, University of Maryland, University of Michigan, University of Minnesota, University of Notre Dame, University of Pittsburgh, University of Texas, University of Wisconsin, University of Wyoming, US Air Force Research Laboratory, Wayne State University, Worcester Polytechnic Institute