Exploiting Nonlinear Algebraic Structure in Matrix Completion

This talk considers matrix completion in cases where columns are points on a nonlinear algebraic variety (in contrast to the commonplace linear subspace model). A special case arises when the columns come from a union of subspaces, a model that has numerous practical applications. We propose a new approach to this problem based on data tensorization (i.e., products of original data) in combination with standard low-rank matrix completion methods. The key insight is that while the original data matrix may not exhibit low-rank structure, often the tensorized data matrix does. The challenge, however, is that the missing data patterns in the tensorized representation are highly structured and far from uniformly random. We show that, under mild assumptions, the observation patterns are generic enough to enable exact recovery.

Video: https://vimeo.com/247883703