2015 MatrixCompletionwithQueries

• (Ruchansky et al., 2015) ⇒ Natali Ruchansky, Mark Crovella, and Evimaria Terzi. (2015). “Matrix Completion with Queries.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783259

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Matrix+Completion+with+Queries
• http://dl.acm.org/citation.cfm?id=2783258.2783259&preflayout=flat#citedby

Quotes

Author Keywords

• Active querying; data mining; matrix completion; recommender systems

Abstract

In many applications, e.g., recommender systems and traffic monitoring, the data comes in the form of a matrix that is only partially observed and low rank. A fundamental data-analysis task for these datasets is matrix completion, where the goal is to accurately infer the entries missing from the matrix. Even when the data satisfies the low-rank assumption, classical matrix-completion methods may output completions with significant error -- in that the reconstructed matrix differs significantly from the true underlying matrix. Often, this is due to the fact that the information contained in the observed entries is insufficient. In this work, we address this problem by proposing an active version of matrix completion, where queries can be made to the true underlying matrix. Subsequently, we design Order&Extend, which is the first algorithm to unify a matrix-completion approach and a querying strategy into a single algorithm. Order&Extend is able identify and alleviate insufficient information by judiciously querying a small number of additional entries. In an extensive experimental evaluation on real-world datasets, we demonstrate that our algorithm is efficient and is able to accurately reconstruct the true matrix while asking only a small number of queries.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 MatrixCompletionwithQueries	Evimaria Terzi Mark Crovella Natali Ruchansky			Matrix Completion with Queries				10.1145/2783258.2783259		2015