[Brown CS Talks] Brown CS Seminar: Petros Drineas in Lubrano on 3/14/02 at noon

[talks-admin@list.cs.brown.edu]

			      CS Seminar
		  
		  The Department of Computer Science
			   BROWN UNIVERSITY

			      
			       presents

			    Petros Drineas

			   Yale University

		   Thursday, March 14, 2002 at noon
	       Lubrano Conference Room (CIT 4th floor)
	       Refreshments will be served at 11:45 am
			       

      Pass Efficient Algorithms for Approximating Large Matrices


			       Abstract

In many applications (e.g. information retrieval, image processing) a
large collection of m objects are implicitly presented as points in an
n-dimensional Euclidean space, where n is the number of features that
describe the objects; such a collection may be represented by an m by
n matrix A. We present algorithms for processing such matrices. Our
algorithms are quite different from traditional numerical analysis
approaches and generally fit the following model: we assume that the
input matrices are prohibitively large to store in RAM and only
external memory storage is possible. We are allowed to read the
matrices a few times and keep a ``sketch'' of the matrices in
RAM. Computing the ``sketch '' should be a very fast process; indeed,
one
of the contributions of our work is to demonstrate that a ``sketch''
consisting only of a random sample of rows and/or columns of the
matrices is adequate for efficient approximations. A crucial issue is
how to form the random sample; we use adaptive sampling, thus keeping
heavier rows/columns with higher probability. Adaptive sampling offers
substantial gains; it allows us to approximately solve problems in
sparse matrices as well as dense matrices. We will present an
algorithm to approximate the product of two (or more) matrices and
experimental results revealing the competitiveness of our algorithm
over full matrix multiplication. We will also present an algorithm to
approximate a matrix A by some other matrix A' of the same dimensions,
which can be ``described'' in much less space. Thus, A' could
potentially be stored in RAM instead of A. Finally, we will present an
application of this approximation to recommendation systems and
collaborative filtering. On the more theoretical side, we will sketch
how A' can be used to efficiently approximate sparse instances of
Max-Cut (and other Max-2-CSP problems).


		     Host:  Professor Steve Reiss