# Provable Inductive Matrix Completion

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2013.

## Built on by (most cited first, 30 of 32)

- [Sample Efficient Linear Meta-Learning by Alternating Minimization](https://mlsanity.com/paper/2105.08306/) (2021)
- [Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems](https://mlsanity.com/paper/2401.07298/) (2024)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits](https://mlsanity.com/paper/2402.11156/) (2024)
- [Inductive Matrix Completion Using Graph Autoencoder](https://mlsanity.com/paper/2108.11124/) (2021)
- [Tensor train completion: local recovery guarantees via Riemannian optimization](https://mlsanity.com/paper/2110.03975/) (2021)
- [Fast quantum state reconstruction via accelerated non-convex programming](https://mlsanity.com/paper/2104.07006/) (2021)
- [Nonparametric Matrix Estimation with One-Sided Covariates](https://mlsanity.com/paper/2110.13969/) (2021)
- [Communicative Subgraph Representation Learning for Multi-Relational Inductive Drug-Gene Interaction Prediction](https://mlsanity.com/paper/2205.05957/) (2022)
- [Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithm](https://mlsanity.com/paper/2201.13052/) (2022)
- [Combining Explicit and Implicit Regularization for Efficient Learning in Deep Networks](https://mlsanity.com/paper/2306.00342/) (2023)
- [Private Matrix Factorization with Public Item Features](https://mlsanity.com/paper/2309.11516/) (2023)
- [One Rank at a Time: Cascading Error Dynamics in Sequential Learning](https://mlsanity.com/paper/2505.22602/) (2025)
- [Generalization Bounds for Inductive Matrix Completion in Low-noise Settings](https://mlsanity.com/paper/2212.08339/) (2022)
- [Item Graph Convolution Collaborative Filtering for Inductive Recommendations](https://mlsanity.com/paper/2303.15946/) (2023)
- [Mixed Matrix Completion in Complex Survey Sampling under Heterogeneous Missingness](https://mlsanity.com/paper/2402.03954/) (2024)
- [Policy Augmentation: An Exploration Strategy for Faster Convergence of Deep Reinforcement Learning Algorithms](https://mlsanity.com/paper/2102.05249/) (2021)
- [Variational Bayesian inference for CP tensor completion with side information](https://mlsanity.com/paper/2206.12486/) (2022)
- [Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution](https://mlsanity.com/paper/2302.03933/) (2023)
- [Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders](https://mlsanity.com/paper/2405.03651/) (2024)
- [Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion](https://mlsanity.com/paper/2411.12965/) (2024)
- [Adaptively-weighted Nearest Neighbors for Matrix Completion](https://mlsanity.com/paper/2505.09612/) (2025)
- [Worst-case low-rank approximations](https://mlsanity.com/paper/2603.11304/) (2026)
- [ModelLens: Finding the Best for Your Task from Myriads of Models](https://mlsanity.com/paper/2605.07075/) (2026)
- [Generating Artificial Core Users for Interpretable Condensed Data](https://mlsanity.com/paper/2102.03674/) (2021)
- [Learning to Schedule in Parallel-Server Queues with Stochastic Bilinear Rewards](https://mlsanity.com/paper/2112.06362/) (2021)
- [LRSVRG-IMC: An SVRG-Based Algorithm for LowRank Inductive Matrix Completion](https://mlsanity.com/paper/2201.08516/) (2022)
- [NRBdMF: A recommendation algorithm for predicting drug effects considering directionality](https://mlsanity.com/paper/2208.04312/) (2022)
- [Differential Privacy of Quantum and Quantum-Inspired Classical Recommendation Algorithms](https://mlsanity.com/paper/2502.04758/) (2025)
- [Robust Matrix Estimation with Side Information](https://mlsanity.com/paper/2603.24833/) (2026)

## Abstract (arXiv)

Consider a movie recommendation system where apart from the ratings information, side information such as user's age or movie's genre is also available. Unlike standard matrix completion, in this setting one should be able to predict inductively on new users/movies. In this paper, we study the problem of inductive matrix completion in the exact recovery setting. That is, we assume that the ratings matrix is generated by applying feature vectors to a low-rank matrix and the goal is to recover back the underlying matrix. Furthermore, we generalize the problem to that of low-rank matrix estimation using rank-1 measurements. We study this generic problem and provide conditions that the set of measurements should satisfy so that the alternating minimization method (which otherwise is a non-convex method with no convergence guarantees) is able to recover back the em exact underlying low-rank matrix. In addition to inductive matrix completion, we show that two other low-rank estimation problems can be studied in our framework: a) general low-rank matrix sensing using rank-1 measurements, and b) multi-label regression with missing labels. For both the problems, we provide novel and interesting bounds on the number of measurements required by alternating minimization to provably converges to the em exact low-rank matrix. In particular, our analysis for the general low rank matrix sensing problem significantly improves the required storage and computational cost than that required by the RIP-based matrix sensing methods citeRechtFP2007. Finally, we provide empirical validation of our approach and demonstrate that alternating minimization is able to recover the true matrix for the above mentioned problems using a small number of measurements.