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
developments.
Powerpoint Slides: http://www.seas.upenn.edu/~jean/quadoptim-talk3.pdf