Petros Drineas is an assistant professor in the computer science department of Rensselaer Polytechnic Institute. His main research interests are the design and analysis of randomized and approximation algorithms for linear algebraic problems, and their applications to information retrieval and data mining.

AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS   Info

MPI Audience

English

60 Minutes

Saarbrücken

The Singular Value Decomposition (SVD) of matrices (and the related Principal Components Analysis) has found numerous applications in extracting structure from datasets in various domains, e.g., the social sciences, biology, chemistry, medicine, Internet data, etc. The extracted structure is expressed in terms of singular vectors, which are linear combinations of all the input data and lack an intuitive physical interpretation. In this talk we shall discuss a matrix decomposition of the form CUR which, given an m-by-n matrix A, approximates A by the product CUR, where C consists of a few columns of A, R consists of a few rows of A, and U is a carefully constructed, constant-sized matrix. Such decompositions might be easier to interpret in applications, since both C and R are subsets of the data.
Previous matrix decompositions of this form only guaranteed additive error approximations. Our construction for C, U, and R takes cubic time and guarantees that the approximation is almost the best possible in the sense of relative error. We will discuss applications of PCA and CUR in the analysis of human genetics data.

Kevin Chang

113

--email hidden

passcode not visible

logged in users only