PhD Final Oral Defense: Matyas Sustik, December 14, 2012, 10:00 AM CST, ACES 4.304

Contact Name: 
Lydia Griffith
Dec 14, 2012 10:00am - 12:00pm

PhD Final Oral Defense: Matyas Sustik

Date: Friday, December 14, 2012
Time: 10:00 AM CST
Place: ACES 4.304
Research Supervisor: Inderjit Dhillon

The title:  Structured Numerical Problems in Contemporary Applications

The presence of structure in a computational problem can often be exploited
and can lead to a more efficient numerical algorithm.  In this dissertation,
we look at structured numerical problems that arise from applications in
wireless communications and machine learning that also impact other areas of
scientific computing.

In wireless communication system designs, certain structured matrices
(frames) need to be generated.  The design of such matrices is equivalent to
a symmetric inverse eigenvalue problem where the values of the diagonal
elements are prescribed.  We present algorithms that are capable of
generating a larger set of these constructions than previous algorithms.  We
also discuss the existence of equiangular tight frames---frames that satisfy
additional structural properties.

Kernel learning is an important class of problems in machine learning. It
often relies on efficient numerical algorithms that solve underlying convex
optimization problems.  In our work, the objective functions to be minimized
are the von Neumann and the LogDet Bregman matrix divergences.  The algorithm
that solves this optimization problem performs matrix updates based on
repeated eigendecompositions of diagonal plus rank-one matrices in the case
of von Neumann matrix divergence, and Cholesky updates in case of the LogDet
Bregman matrix divergence. Our contribution exploits the low-rank
representations and the structure of the constraint matrices, resulting in
more efficient algorithms than previously known.

We also present two specialized zero-finding algorithms where we exploit the
structure through the shape and exact formulation of the objective
function. The first zero-finding task arises during the matrix update step
which is part of the above-mentioned kernel learning application.  The second
zero-finding problem is for the secular equation; it is equivalent to the
computation of the eigenvalues of a diagonal plus rank-one matrix. The
secular equation arises in various applications, the most well-known is the
divide-and-conquer eigensolver. In our solutions, we build upon a somewhat
forgotten zero-finding method by P. Jarratt, first described in 1966. The
method employs first derivatives only and needs the same amount of
evaluations as Newton's method, but converges faster.  Our contributions are
the more efficient specialized zero-finding algorithms.