# An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 46 references that are in the map.
- First posted on arXiv 31 Mar 2025.

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

- [FedPara: Low-Rank Hadamard Product for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2108.06098/) (2021)
- [Low-Rank Matrix Completion: A Contemporary Survey](https://mlsanity.com/paper/1907.11705/) (2019)
- [Subtractive Mixture Models via Squaring: Representation and Learning](https://mlsanity.com/paper/2310.00724/) (2023)
- [Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion](https://mlsanity.com/paper/1804.04310/) (2018)
- [Matrix completion with data-dependent missingness probabilities](https://mlsanity.com/paper/2106.02290/) (2021)
- [Accelerating Nonnegative Matrix Factorization Algorithms using Extrapolation](https://mlsanity.com/paper/1805.06604/) (2018)
- [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)
- [A Survey on Matrix Completion: Perspective of Signal Processing](https://mlsanity.com/paper/1901.10885/) (2019)
- [A Neural Network Alternative to Non-Negative Audio Models](https://mlsanity.com/paper/1609.03296/) (2016)
- [Global and Local Analyses of Nonlinear Low-Rank Matrix Recovery Problems](https://mlsanity.com/paper/2010.04349/) (2020)
- [A Momentum Accelerated Algorithm for ReLU-based Nonlinear Matrix Decomposition](https://mlsanity.com/paper/2402.02442/) (2024)
- [Symmetric Matrix Completion with ReLU Sampling](https://mlsanity.com/paper/2406.05822/) (2024)
- [An Accelerated Alternating Partial Bregman Algorithm for ReLU-based Matrix Decomposition](https://mlsanity.com/paper/2503.02386/) (2025)
- [Nonlinear matrix recovery using optimization on the Grassmann manifold](https://mlsanity.com/paper/2109.06095/) (2021)

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

- [Alternating Direction Method of Multipliers for Nonlinear Matrix Decompositions](https://mlsanity.com/paper/2512.17473/) (2025)
- [Manifold-based Algorithms for the Hadamard Decomposition](https://mlsanity.com/paper/2605.28980/) (2026)
- [On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization](https://mlsanity.com/paper/2607.04875/) (2026)
- [Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure](https://mlsanity.com/paper/2608.21607/) (2026)

## Abstract (arXiv)

ReLU matrix decomposition (RMD) is the following problem: given a sparse, nonnegative matrix X and a factorization rank r, identify a rank-r matrix Theta such that X≈ max(0,Theta). RMD is a particular instance of nonlinear matrix decomposition (NMD) that finds application in data compression, matrix completion with entries missing not at random, and manifold learning. The standard RMD model minimizes the least squares error, that is, |X - max(0,Theta)|F2. The corresponding optimization problem, Least-Squares RMD (LS-RMD), is nondifferentiable and highly nonconvex. This motivated Saul to propose an alternative model, revisedubbed Latent-RMD, where a latent variable Z is introduced and satisfies max(0,Z)=X while minimizing |Z - Theta|F2 (``A nonlinear matrix decomposition for mining the zeros of sparse data'', SIAM J. Math. Data Sci., 2022). Our first contribution is to show that the two formulations may yield different low-rank solutions Theta. We then consider a reparametrization of the Latent-RMD, called 3B-RMD, in which Theta is substituted by a low-rank product WH, where W has r columns and H has r rows. Our second contribution is to prove the convergence of a block coordinate descent (BCD) approach applied to 3B-RMD. Our third contribution is a novel extrapolated variant of BCD, dubbed eBCD, which we prove is also convergent under mild assumptions. We illustrate the significant acceleration effect of eBCD compared to eBCD, and also show that eBCD performs well against the state of the art on synthetic and real-world data sets.