Seminar: November 25, 2008, 12:30pm
Michael W. Mahoney, Stanford University
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. 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.