THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Talk
Algebraic Variety Models for High-Rank Matrix Completion
Greg Ongie · Laura Balzano · Rebecca Willett · Robert Nowak

Tue Aug 08 09:06 PM -- 09:24 PM (PDT) @ C4.4
in Robust Estimation »

We consider a non-linear generalization of low-rank matrix completion to the case where the data belongs to an algebraic variety, i.e., each data point is a solution to a system of polynomial equations. In this case the original matrix is possibly high-rank, but it becomes low-rank after mapping each column to a higher dimensional space of monomial features. Algebraic varieties capture a range of well-studied linear models, including affine subspaces and their union, but also quadratic and higher degree curves and surfaces. We study the sampling requirements for a general variety model with a focus on the union of affine subspaces. We propose an efficient matrix completion algorithm that minimizes a convex or non-convex surrogate of the rank of the lifted matrix. Our algorithm uses the well-known "kernel trick'' to avoid working directly with the high-dimensional lifted data matrix and scales efficiently with data size. We show the proposed algorithm is able to recover synthetically generated data up to the predicted sampling complexity bounds. The algorithm also outperforms standard techniques in experiments with real data.

[ PDF]  [ ss Summary/Notes]  [ Video] 

Author Information

Greg Ongie (University of Michigan)
Laura Balzano (University of Michigan)
Rebecca Willett (UW Madison)
Robert Nowak (University of Wisconsion-Madison)
Robert Nowak

Robert Nowak holds the Nosbusch Professorship in Engineering at the University of Wisconsin-Madison, where his research focuses on signal processing, machine learning, optimization, and statistics.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors