Low-Rank Matrix Completion: Natali Ruchansky, PhD Oral Exam

10:00 am on Friday, April 18, 2014
12:00 pm on Friday, April 18, 2014
MCS 148
Abstract: In the matrix-completion problem the goal is to accurately infer the missing entries of a partially-observed matrix. Although the problem dates back to the 1980's, it has received an explosion of recent attention due to the observation that an abundance of data matrices are in fact low-rank. This newfound interest yielded algorithms capable of solving the low-rank matrix completion even with the vast majority of matrix elements missing. In this talk we explore the two main classes of low-rank matrix completion approaches. The first class, which we call 'statistical', revolves around particular sampling assumptions and an optimization strategy. The second class, which we call 'structural', draws connections to algebraic graph theory and epidemic propagation in networks. These methods are capable of revealing how many completions are possible for a given matrix, and in particular of whether a unique completion exists. Using the LMAFit and ICMC algorithms as examples of statistical and structural methods respectively, we will demonstrate the crux of each class of approaches and the fundamental differences between them. Committee: Evimaria Terzi Mark Crovella Luis Carvalho