ACO The ACO Seminar (2010-2011)

Oct. 18, 4pm, Wean 8220 *** NON-STANDARD DAY/TIME ***
Ravi Kannan, Microsoft Research Labs., India
Some Curious 0-1 theorems

Abstract:

For a matrix A, the vector maximizing |Ax|/|x| is the top singular vector; the maximum value is the top singular value. Our first theorem: For any m × n matrix A, there is a? vector y such that |Ay|/|y| is at least the top 0-1 singular value divided by c ln n. Such a y can be found in polynomial time. This is the best possible factor. We will also give an extension to the top k singular vectors. Our second theorem: a matrix of rank r can be (arbitrarily well) approxi- mated by the sum of r × POLYLOG rank-1 matrices, where, each rank-1 matrix is of the form ?uT v, ?, a scaler and u, v are 0-1 vectors. This is also constructive. The proofs are relatively simple. Two open questions: (i) Are such theorems known and (ii) find applications.

Joint work with Amit Deshpande and Nikhil Srivatsav


Back to the ACO home page