Matrix Completion with Noisy Side Information | Center for Big Data Analytics

Abstract: We study the matrix completion problem with side information. Side information has been considered in several matrix completion applications, and has been empirically shown to be useful in many cases. Recently, researchers studied the effect of side information for matrix completion from a theoretical viewpoint, showing that sample complexity can be significantly reduced given completely clean features. However, since in reality most given features are noisy or only weakly informative, the development of a model to handle a {it general} feature set, and investigation of how much noisy features can help matrix recovery, remains an important issue. In this paper, we propose a novel model that balances between features and observations simultaneously in order to leverage feature information yet be robust to feature noise. Moreover, we study the effect of general features in theory and show that by using our model, the sample complexity can be lower than matrix completion as long as features are sufficiently informative. This result provides a theoretical insight into the usefulness of general side information. Finally, we consider synthetic data and two applications — relationship prediction and semi-supervised clustering — and show that our model outperforms other methods for matrix completion that use features both in theory and practice.

Download: pdf

Citation

Matrix Completion with Noisy Side Information (pdf, software)
K. Chiang, C. Hsieh, I. Dhillon.
In Neural Information Processing Systems (NIPS), pp. 3447–3455, December 2015. (Spotlight)

Bibtex:
@inproceedings{chiang2015matrixcom, author = "Kai-Yang Chiang AND Cho-Jui Hsieh AND Inderjit S. Dhillon", title = "Matrix Completion with Noisy Side Information", booktitle = "Neural Information Processing Systems (NIPS)", page = "3447—-3455", year = "2015", month = "dec", abstract = "We study the matrix completion problem with side information. Side information has been considered in several matrix completion applications, and has been empirically shown to be useful in many cases. Recently, researchers studied the effect of side information for matrix completion from a theoretical viewpoint, showing that sample complexity can be significantly reduced given completely clean features. However, since in reality most given features are noisy or only weakly informative, the development of a model to handle a {it general} feature set, and investigation of how much noisy features can help matrix recovery, remains an important issue. In this paper, we propose a novel model that balances between features and observations simultaneously in order to leverage feature information yet be robust to feature noise. Moreover, we study the effect of general features in theory and show that by using our model, the sample complexity can be lower than matrix completion as long as features are sufficiently informative. This result provides a theoretical insight into the usefulness of general side information. Finally, we consider synthetic data and two applications — relationship prediction and semi-supervised clustering — and show that our model outperforms other methods for matrix completion that use features both in theory and practice." }