Tuesday, January 30, 2007
4:15 pm
5130 Upson Hall

Computer Science
Colloquium
Spring 2007

Plamen Koev
Department of Mathematics
Massachusetts Institute of Technology

 

Computation of Accurate Eigenvalues and its Applications - from Electrical Impedance Tomography to 3D Target Recognition


Eigenvalue computation has pervasive applications across most branches of science and engineering. In this talk I will present our recent highly accurate and efficient algorithms for structured eigenvalue problems.

In finite precision computations the accuracy of the tiniest eigenvalues can quickly be lost to round-off errors. This is unfortunate since these tiny eigenvalues are often very accurately determined by the data and are of considerable physical significance. For example, in Electrical Impedance Tomography, the SVD of a particular Vandermonde matrix allows us to recover the conductivity of the interior of an object. A similar approach in inverse scattering gives rise to the same computational problem. Another example is 3D target recognition in which the eigenvalues of the covariance matrix of a vehicle's 3D coordinates become the 'signature' that can be used to recognize the vehicle; this method is independent of the angle of observation and hence overcomes a major drawback in two dimensions.

The foregoing applications are examples of problems that have benefited immensely from the new highly accurate eigenvalue algorithms that we have developed. Our algorithms, unlike the conventional ones, respect and exploit the underlying combinatorial and algebraic matrix structure and compute all eigenvalues to high relative accuracy without the need for extra precision.

In the talk I will focus in particular on our new algorithm for computing eigenvalues of random matrices, a computational problem whose solution has eluded researchers for over 40 years.

Dr. Koev did his doctoral work under the supervision of Professor James Demmel and received his Ph.D. in mathematics from the University of California, Berkeley in 2002. He is currently a postdoctoral researcher in the mathematics department at M.I.T. His interests are in accurate and efficient matrix computations, applied multivariate statistical analysis and random matrix theory.