Oct. 18, 4pm, Wean 8220 *** NON-STANDARD DAY/TIME ***

Ravi Kannan, Microsoft Research Labs., India

Some Curious 0-1 theorems

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