Algebraic Variety Models for High-Rank Matrix Completion

Greg Ongie, Rebecca Willett, Robert D. Nowak, Laura Balzano
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:2691-2700, 2017.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-ongie17a, title = {Algebraic Variety Models for High-Rank Matrix Completion}, author = {Greg Ongie and Rebecca Willett and Robert D. Nowak and Laura Balzano}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {2691--2700}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/ongie17a/ongie17a.pdf}, url = {https://proceedings.mlr.press/v70/ongie17a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Algebraic Variety Models for High-Rank Matrix Completion %A Greg Ongie %A Rebecca Willett %A Robert D. Nowak %A Laura Balzano %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-ongie17a %I PMLR %P 2691--2700 %U https://proceedings.mlr.press/v70/ongie17a.html %V 70 %X 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.
APA
Ongie, G., Willett, R., Nowak, R.D. & Balzano, L.. (2017). Algebraic Variety Models for High-Rank Matrix Completion. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:2691-2700 Available from https://proceedings.mlr.press/v70/ongie17a.html.

Related Material