# Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithm

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 47 references that are in the map.
- First posted on arXiv 31 Jan 2022.

## Builds on (most cited first, 12 of 12)

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Global Optimality in Low-rank Matrix Optimization](https://mlsanity.com/paper/1702.07945/) (2017)
- [Provable Inductive Matrix Completion](https://mlsanity.com/paper/1306.0626/) (2013)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow](https://mlsanity.com/paper/1803.01233/) (2018)
- [Local and Global Linear Convergence of General Low-rank Matrix Recovery Problems](https://mlsanity.com/paper/2104.13348/) (2021)
- [The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization](https://mlsanity.com/paper/2003.10981/) (2020)
- [A Nonconvex Projection Method for Robust PCA](https://mlsanity.com/paper/1805.07962/) (2018)
- [Geometry of Factored Nuclear Norm Regularization](https://mlsanity.com/paper/1704.01265/) (2017)
- [Collaborative Self-Attention for Recommender Systems](https://mlsanity.com/paper/1905.13133/) (2019)

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

- [MFAI: A Scalable Bayesian Matrix Factorization Approach to Leveraging Auxiliary Information](https://mlsanity.com/paper/2303.02566/) (2023)
- [Tensor Completion Leveraging Graph Information: A Dynamic Regularization Approach with Statistical Guarantees](https://mlsanity.com/paper/2310.02543/) (2023)
- [Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approach](https://mlsanity.com/paper/2502.08536/) (2025)
- [Sample-efficient inductive matrix completion with noise and inexact side-information](https://mlsanity.com/paper/2605.17189/) (2026)

## Abstract (arXiv)

The inductive matrix completion (IMC) problem is to recover a low rank matrix from few observed entries while incorporating prior knowledge about its row and column subspaces. In this work, we make three contributions to the IMC problem: (i) we prove that under suitable conditions, the IMC optimization landscape has no bad local minima; (ii) we derive a simple scheme with theoretical guarantees to estimate the rank of the unknown matrix; and (iii) we propose GNIMC, a simple Gauss-Newton based method to solve the IMC problem, analyze its runtime and derive recovery guarantees for it. The guarantees for GNIMC are sharper in several aspects than those available for other methods, including a quadratic convergence rate, fewer required observed entries and stability to errors or deviations from low-rank. Empirically, given entries observed uniformly at random, GNIMC recovers the underlying matrix substantially faster than several competing methods.