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:
Notes
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
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 |