2009 Poster Sessions : Matrix Completion from a Few Entries

Student Name : Raghunandan Keshavan, Sewoong Oh
Advisor : Andrea Montanari
Research Areas: Information Systems
Abstract:
Let M be a random (alpha n) x n matrix of rank r<
This settles (in the case of bounded rank) a question left open by Candes and Recht and improves over the guarantees for their reconstruction algorithm. The complexity of our algorithm is O(|E|r log(n)), which opens the way to its use for massive data sets. In the process of proving these statements, we obtain a generalization of a celebrated result by Friedman-Kahn-Szemeredi and Feige-Ofek on the spectrum of sparse random matrices.


Bio:
Raghunandan H. Keshavan is a PhD candidate at the Dept. of Electrical Engineering, Stanford University. He works under the supervision of Prof. Andrea Montanari. He received his Master's degree in Electrical Engineering from Stanford University in Jan. 2009 and his Bachelor's degree in Electrical Engineering from the Indian Institute of Technology Madras in August 2007.

Sewoong Oh is a Ph.D. candidate at the department of Electrical Engineering at Stanford University. He works with Professor Andrea Montanari in the area of coding theory. He received his Master's degree in Electrical Engineering from Stanford University in June 2007. He graduated from Seoul National University, Korea, with a Bachelor of Science in Electrical Engineering (1998).