[Colloquium] Talk by Michael W. Mahoney - Tomorrow

[Nita Yack]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, November 25, 2008
Time: 12:30 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Michael Mahoney

From:		Stanford University

Web page:	 http://cs.stanford.edu/people/mmahoney/

Title:    Statistical Leverage and Improved Matrix Algorithms

Abstract:  Given an m x n matrix A and a rank parameter k, define the  
leverage of the i-th row of A to be the i-th diagonal element of the  
projection matrix onto the span of the top k left singular vectors of  
A.  Historically, this statistical concept (and generalizations of it)  
has found extensive applications in, e.g, diagnostic regression  
analysis.  Recently, this concept has been central in the development  
of improved algorithms for several fundamental matrix problems.  Two  
examples of this will be described.  The first problem is the least  
squares approximation problem, in which there are n constraints and d  
variables.  Classical algorithms, dating back to Gauss and Legendre,  
use O(nd2) time.  We describe a randomized algorithm that uses only  
roughly O(n d log d) time to compute a relative-error, i.e., 1+/- 
epsilon, approximation.  The second problem is the problem of  
selecting a ``good'' set of exactly k columns from an m x n matrix,  
and the algorithm of Gu and Eisenstat provides the best previously  
existing result.  We describe a two-stage algorithm that improves on  
their result (assuming that k is small).  Recent application of these  
ideas in modern statistical data analysis will be briefly described.

Refreshments will be served prior to the talk in RY 255 at 12:00.

Nita

**************************
Nita Yack
Departmental Administrator
Computer Science Department
1100 E. 58th Street - Room 151
Chicago, IL 60637
(773) 702-6019
(773) 702-8487 FAX

"Hard work spotlights the character of people: some turn up their  
sleeves, some turn up their noses, and some don't turn up at all."


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20081124/936a5c54/attachment-0001.htm