Convolutional Imputation of Matrix Networks

Qingyun Sun, Mengyuan Yan, David Donoho,  boyd
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:4818-4827, 2018.

Abstract

A matrix network is a family of matrices, with their relations modeled as a weighted graph. We consider the task of completing a partially observed matrix network. The observation comes from a novel sampling scheme where a fraction of matrices might be completely unobserved. How can we recover the entire matrix network from incomplete observations? This mathematical problem arises in many applications including medical imaging and social networks. To recover the matrix network, we propose a structural assumption that the matrices are low-rank after the graph Fourier transform on the network. We formulate a convex optimization problem and prove an exact recovery guarantee for the optimization problem. Furthermore, we numerically characterize the exact recovery regime for varying rank and sampling rate and discover a new phase transition phenomenon. Then we give an iterative imputation algorithm to efficiently solve optimization problem and complete large scale matrix networks. We demonstrate the algorithm with a variety of applications such as MRI and Facebook user network.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-sun18d, title = {Convolutional Imputation of Matrix Networks}, author = {Sun, Qingyun and Yan, Mengyuan and Donoho, David and stephen boyd}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {4818--4827}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/sun18d/sun18d.pdf}, url = {https://proceedings.mlr.press/v80/sun18d.html}, abstract = {A matrix network is a family of matrices, with their relations modeled as a weighted graph. We consider the task of completing a partially observed matrix network. The observation comes from a novel sampling scheme where a fraction of matrices might be completely unobserved. How can we recover the entire matrix network from incomplete observations? This mathematical problem arises in many applications including medical imaging and social networks. To recover the matrix network, we propose a structural assumption that the matrices are low-rank after the graph Fourier transform on the network. We formulate a convex optimization problem and prove an exact recovery guarantee for the optimization problem. Furthermore, we numerically characterize the exact recovery regime for varying rank and sampling rate and discover a new phase transition phenomenon. Then we give an iterative imputation algorithm to efficiently solve optimization problem and complete large scale matrix networks. We demonstrate the algorithm with a variety of applications such as MRI and Facebook user network.} }
Endnote
%0 Conference Paper %T Convolutional Imputation of Matrix Networks %A Qingyun Sun %A Mengyuan Yan %A David Donoho %A boyd %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-sun18d %I PMLR %P 4818--4827 %U https://proceedings.mlr.press/v80/sun18d.html %V 80 %X A matrix network is a family of matrices, with their relations modeled as a weighted graph. We consider the task of completing a partially observed matrix network. The observation comes from a novel sampling scheme where a fraction of matrices might be completely unobserved. How can we recover the entire matrix network from incomplete observations? This mathematical problem arises in many applications including medical imaging and social networks. To recover the matrix network, we propose a structural assumption that the matrices are low-rank after the graph Fourier transform on the network. We formulate a convex optimization problem and prove an exact recovery guarantee for the optimization problem. Furthermore, we numerically characterize the exact recovery regime for varying rank and sampling rate and discover a new phase transition phenomenon. Then we give an iterative imputation algorithm to efficiently solve optimization problem and complete large scale matrix networks. We demonstrate the algorithm with a variety of applications such as MRI and Facebook user network.
APA
Sun, Q., Yan, M., Donoho, D. & boyd, . (2018). Convolutional Imputation of Matrix Networks. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:4818-4827 Available from https://proceedings.mlr.press/v80/sun18d.html.

Related Material