The ACO Seminar (2010-2011)

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