[BANANA] LA/Opt seminar Wed April 16 (Michael Mahoney)

[Michael A. Saunders]

Remember: NEW ROOM this quarter

   Linear Algebra and Optimization Seminar (CME510)
   iCME, Stanford University
   http://icme.stanford.edu/seminars/seminars.php

   4:15pm Wed April 16, 2008
   Room GESB134 (Green Earth Sciences Building)

   Dr Michael Mahoney
   Yahoo! Research
   Sunnyvale, CA
   mahoney at yahoo-inc.com
   http://www.cs.yale.edu/homes/mmahoney/

   Statistical leverage and improved matrix algorithms

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.  Very recently, this concept has been central in the
development of improved algorithms for several fundamental matrix
problems.  Two examples 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(nd^2) 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
not extremely large).  Recent application of these ideas in modern
statistical data analysis will be briefly described.