# Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2018.

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

- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithm](https://mlsanity.com/paper/2201.13052/) (2022)
- [Matrix Completion in Almost-Verification Time](https://mlsanity.com/paper/2308.03661/) (2023)
- [Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing](https://mlsanity.com/paper/2101.05113/) (2021)
- [Generalization Bounds for Inductive Matrix Completion in Low-noise Settings](https://mlsanity.com/paper/2212.08339/) (2022)
- [Generating Artificial Core Users for Interpretable Condensed Data](https://mlsanity.com/paper/2102.03674/) (2021)
- [LRSVRG-IMC: An SVRG-Based Algorithm for LowRank Inductive Matrix Completion](https://mlsanity.com/paper/2201.08516/) (2022)
- [Sample-efficient inductive matrix completion with noise and inexact side-information](https://mlsanity.com/paper/2605.17189/) (2026)

## Abstract (arXiv)

We revisit the inductive matrix completion problem that aims to recover a rank-r matrix with ambient dimension d given n features as the side prior information. The goal is to make use of the known n features to reduce sample and computational complexities. We present and analyze a new gradient-based non-convex optimization algorithm that converges to the true underlying matrix at a linear rate with sample complexity only linearly depending on n and logarithmically depending on d. To the best of our knowledge, all previous algorithms either have a quadratic dependency on the number of features in sample complexity or a sub-linear computational convergence rate. In addition, we provide experiments on both synthetic and real world data to demonstrate the effectiveness of our proposed algorithm.