Timezone: »
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.
Summary/Notes]
Author Information
Greg Ongie (University of Michigan)
Laura Balzano (University of Michigan)
Rebecca Willett (UW Madison)
Robert Nowak (University of Wisconsion-Madison)
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)
-
2017 Talk: Algebraic Variety Models for High-Rank Matrix Completion »
Wed Aug 9th 04:06 -- 04:24 AM Room C4.4
More from the Same Authors
-
2021 : On the Sparsity of Deep Neural Networks in the Overparameterized Regime: An Empirical Study »
Rahul Parhi · Jack Wolf · Robert Nowak -
2021 : Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Bounds »
Yahya Sattar · Zhe Du · Davoud Ataee Tarzanagh · Necmiye Ozay · Laura Balzano · Samet Oymak -
2020 Poster: Robust Outlier Arm Identification »
Yinglun Zhu · Sumeet Katariya · Robert Nowak -
2020 Poster: Preference Modeling with Context-Dependent Salient Features »
Amanda Bower · Laura Balzano -
2019 Poster: Bilinear Bandits with Low-rank Structure »
Kwang-Sung Jun · Rebecca Willett · Stephen Wright · Robert Nowak -
2019 Oral: Bilinear Bandits with Low-rank Structure »
Kwang-Sung Jun · Rebecca Willett · Stephen Wright · Robert Nowak -
2019 Tutorial: Active Learning: From Theory to Practice »
Robert Nowak · Steve Hanneke -
2017 Poster: Leveraging Union of Subspace Structure to Improve Constrained Clustering »
John Lipor · Laura Balzano -
2017 Talk: Leveraging Union of Subspace Structure to Improve Constrained Clustering »
John Lipor · Laura Balzano