# Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 118 references that are in the map.
- First posted on arXiv 21 Aug 2026.

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

- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precision](https://mlsanity.com/paper/2407.08608/) (2024)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [FlashAttention-4: Algorithm and Kernel Pipelining Co-Design for Asymmetric Hardware Scaling](https://mlsanity.com/paper/2603.05451/) (2026)
- [Probabilistic Latent Semantic Analysis](https://mlsanity.com/paper/1301.6705/) (2013)
- [Generalized Low Rank Models](https://mlsanity.com/paper/1410.0342/) (2014)
- [Low-Rank Matrix Completion: A Contemporary Survey](https://mlsanity.com/paper/1907.11705/) (2019)
- [Practical sketching algorithms for low-rank matrix approximation](https://mlsanity.com/paper/1609.00048/) (2016)
- [The Sparse Manifold Transform](https://mlsanity.com/paper/1806.08887/) (2018)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [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)
- [Additive and multiplicative effects network models](https://mlsanity.com/paper/1807.08038/) (2018)
- [1-Bit Matrix Completion under Exact Low-Rank Constraint](https://mlsanity.com/paper/1502.06689/) (2015)
- [Categorical Matrix Completion](https://mlsanity.com/paper/1507.00421/) (2015)
- [Probabilistic low-rank matrix completion on finite alphabets](https://mlsanity.com/paper/1412.2632/) (2014)
- [Bounded Simplex-Structured Matrix Factorization: Algorithms, Identifiability and Applications](https://mlsanity.com/paper/2209.12638/) (2022)
- [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)
- [When big data actually are low-rank, or entrywise approximation of certain function-generated matrices](https://mlsanity.com/paper/2407.03250/) (2024)
- [Alternating Direction Method of Multipliers for Nonlinear Matrix Decompositions](https://mlsanity.com/paper/2512.17473/) (2025)
- [Noisy Matrix Completion under Sparse Factor Models](https://mlsanity.com/paper/1411.0282/) (2014)
- [Nonnegative Low Rank Matrix Approximation for Nonnegative Matrices](https://mlsanity.com/paper/1912.06836/) (2019)
- [An Efficient Alternating Algorithm for ReLU-based Symmetric Matrix Decomposition](https://mlsanity.com/paper/2503.16846/) (2025)

## Abstract (arXiv)

We investigate when a sparse nonnegative matrix can be recovered from a real-valued matrix of much lower rank by zeroing out its negative elements. The potential for such decompositions suggests a mathematical connection between sparsity and rank; we analyze a number of sparse matrices with this latent low-rank structure and use them to illustrate the geometric origins of this connection. Previous algorithms have discovered these decompositions via an alternating minimization over the factors of a low-rank matrix, but to do so, they have also needed to compute and store another matrix, neither sparse nor low-rank, that is the size of their product. We develop a stochastic, alternating least-squares algorithm that operates on smaller blocks of this dense matrix and scales as a result to much larger problems. We also show how to further accelerate this algorithm with sparse optimizations and customized CUDA kernels. As one example, we use the algorithm to analyze the sparse matrix of synaptic weights for the recently published textitDrosphilia connectome. The nonzero elements of this matrix, with 139,255 rows and columns, record the number of synapses between cells in the nervous system of a female fruit fly. Despite a slowly decaying spectrum of singular values, this matrix exhibits a latent low-rank structure that is predictive of cell categories across multiple levels of specificity.