Loading Events

« All Events

  • This event has passed.

Fall 2010 GRASP Seminar – Jean Gallier, University of Pennsylvania, “Quadratic Optimization Problems Arising in Computer Vision”

October 8, 2010 @ 11:00 am - 12:00 pm

Abstract: Computer
vision problems such as contour grouping often lead to quadratic optimization
problems. We begin by reviewing the problem of finding the maximum of a
quadratic function, f(x) = x^T A x, on the unit sphere. Then, we describe a
contour grouping problem studied by Jianbo Shi and Qihui Zhu. We present Shi’s
objective function (involving certain kinds of cuts in a weighted graph). Since
this maximization problem is hard, we present Shi’s relaxation of the problem
and we show that a simpler formula can be obtained (in term of a weight matrix,
P). This new formulation involves an Hermitian matrix, H(delta), depending on a
parameter. To study the variation of the top eigenvalue of this matrix, we show
how to compute the derivative of an eigenvalue and of a corresponding
eigenvector. The literature on this topic is either messy or incomplete. It
turns out that the eigenvalues of H(delta) are related to the field of values of
the matrix P, a concept introduced by Hausdorff and Toeplitz in 1918. I will
show some Matlab plots due to Ryan Kennedy to illustrate these new

Powerpoint Slides: http://www.seas.upenn.edu/~jean/quadoptim-talk3.pdf


- Learn More

Gallier is a Professor of Computer and Information Science at the University of
Pennsylvania, with a secondary appointment in Mathematics. He obtained his Ph.D
in Computer Science at UCLA in 1978. Gallier has done research in a number of
areas of CS, including program correctness, incremental parsing and error
recovery, logic programming, unification, term-rewriting and equational logic,
polymorphic lambda calculi, and linear logic. For the past fifteen years, he
has focused on geometric modeling, surfaces splines, surface reconstruction
from meshes and recently on optimization problems arising in computer vision.
Generally, he is interested in applying differential and algebraic geometry
tools to problems in computer science. He is the author of four books, the last
one, “Discrete Mathematics”, to appear in the UTM Springer series


October 8, 2010
11:00 am - 12:00 pm
Event Category: