# Accelerated Algorithms for Nonlinear Matrix Decomposition with the ReLU function

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 13 references that are in the map.
- First posted on arXiv 15 May 2023.

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

- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Accelerating Nonnegative Matrix Factorization Algorithms using Extrapolation](https://mlsanity.com/paper/1805.06604/) (2018)

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

- [Kissing to Find a Match: Efficient Low-Rank Permutation Representation](https://mlsanity.com/paper/2308.13252/) (2023)
- [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)
- [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)
- [Manifold-based Algorithms for the Hadamard Decomposition](https://mlsanity.com/paper/2605.28980/) (2026)
- [An Efficient Alternating Algorithm for ReLU-based Symmetric Matrix Decomposition](https://mlsanity.com/paper/2503.16846/) (2025)
- [Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure](https://mlsanity.com/paper/2608.21607/) (2026)

## Abstract (arXiv)

In this paper, we study the following nonlinear matrix decomposition (NMD) problem: given a sparse nonnegative matrix X, find a low-rank matrix Theta such that X ≈ f(Theta), where f is an element-wise nonlinear function. We focus on the case where f(·) = max(0, ·), the rectified unit (ReLU) non-linear activation. We refer to the corresponding problem as ReLU-NMD. We first provide a brief overview of the existing approaches that were developed to tackle ReLU-NMD. Then we introduce two new algorithms: (1) aggressive accelerated NMD (A-NMD) which uses an adaptive Nesterov extrapolation to accelerate an existing algorithm, and (2) three-block NMD (3B-NMD) which parametrizes Theta = WH and leads to a significant reduction in the computational cost. We also propose an effective initialization strategy based on the nuclear norm as a proxy for the rank function. We illustrate the effectiveness of the proposed algorithms (available on gitlab) on synthetic and real-world data sets.