# Matrix completion with queries

arXiv: https://arxiv.org/abs/1705.00399 · HTML: https://mlsanity.com/paper/1705.00399/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2017.

## Built on by (most cited first, 5 of 5)

- [Matrix Completion with Heterogonous Cost](https://mlsanity.com/paper/2203.12120/) (2022)
- [Survey of Matrix Completion Algorithms](https://mlsanity.com/paper/2204.01532/) (2022)
- [Active Learning for Video Classification with Frame Level Queries](https://mlsanity.com/paper/2307.05587/) (2023)
- [Optimal Transfer Learning for Missing Not-at-Random Matrix Completion](https://mlsanity.com/paper/2503.00174/) (2025)
- [Low Rank Learning for Offline Query Optimization](https://mlsanity.com/paper/2504.06399/) (2025)

## Abstract (arXiv)

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.