# Symmetric Matrix Completion with ReLU Sampling

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 61 references that are in the map.
- First posted on arXiv 9 Jun 2024.

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

- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Learning ReLUs via Gradient Descent](https://mlsanity.com/paper/1705.04591/) (2017)
- [Causal Matrix Completion](https://mlsanity.com/paper/2109.15154/) (2021)
- [Low-Rank Matrix Completion: A Contemporary Survey](https://mlsanity.com/paper/1907.11705/) (2019)
- [Identifiable Generative Models for Missing Not at Random Data Imputation](https://mlsanity.com/paper/2110.14708/) (2021)
- [Missing Not at Random in Matrix Completion: The Effectiveness of Estimating Missingness Probabilities Under a Low Nuclear Norm Assumption](https://mlsanity.com/paper/1910.12774/) (2019)
- [Imputation and low-rank estimation with Missing Not At Random data](https://mlsanity.com/paper/1812.11409/) (2018)
- [Matrix completion with data-dependent missingness probabilities](https://mlsanity.com/paper/2106.02290/) (2021)
- [A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion](https://mlsanity.com/paper/1503.02596/) (2015)
- [Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion](https://mlsanity.com/paper/2204.03316/) (2022)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [New characterizations of Hoffman constants for systems of linear constraints](https://mlsanity.com/paper/1905.02894/) (2019)
- [Accelerated Algorithms for Nonlinear Matrix Decomposition with the ReLU function](https://mlsanity.com/paper/2305.08687/) (2023)
- [Matrix Completion Under Monotonic Single Index Models](https://mlsanity.com/paper/1512.08787/) (2015)
- [Spectral Compressed Sensing via Structured Matrix Completion](https://mlsanity.com/paper/1304.4610/) (2013)
- [Matrix completion with deterministic pattern - a geometric perspective](https://mlsanity.com/paper/1802.00047/) (2018)
- [Tensor Methods for Nonlinear Matrix Completion](https://mlsanity.com/paper/1804.10266/) (2018)
- [TenIPS: Inverse Propensity Sampling for Tensor Completion](https://mlsanity.com/paper/2101.00323/) (2021)
- [Matrix Completion from General Deterministic Sampling Patterns](https://mlsanity.com/paper/2306.02283/) (2023)
- [Representation Learning and Recovery in the ReLU Model](https://mlsanity.com/paper/1803.04304/) (2018)

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

- [An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function](https://mlsanity.com/paper/2503.23832/) (2025)
- [Alternating Direction Method of Multipliers for Nonlinear Matrix Decompositions](https://mlsanity.com/paper/2512.17473/) (2025)
- [On subdifferential chain rule of matrix factorization and beyond](https://mlsanity.com/paper/2410.05022/) (2024)
- [Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure](https://mlsanity.com/paper/2608.21607/) (2026)

## Abstract (arXiv)

We study the problem of symmetric positive semi-definite low-rank matrix completion (MC) with deterministic entry-dependent sampling. In particular, we consider rectified linear unit (ReLU) sampling, where only positive entries are observed, as well as a generalization to threshold-based sampling. We first empirically demonstrate that the landscape of this MC problem is not globally benign: Gradient descent (GD) with random initialization will generally converge to stationary points that are not globally optimal. Nevertheless, we prove that when the matrix factor with a small rank satisfies mild assumptions, the nonconvex objective function is geodesically strongly convex on the quotient manifold in a neighborhood of a planted low-rank matrix. Moreover, we show that our assumptions are satisfied by a matrix factor with i.i.d. Gaussian entries. Finally, we develop a tailor-designed initialization for GD to solve our studied formulation, which empirically always achieves convergence to the global minima. We also conduct extensive experiments and compare MC methods, investigating convergence and completion performance with respect to initialization, noise level, dimension, and rank.