# Stochastic Subsampling for Factorizing Huge Matrices

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jan 2017.

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

- [Joint Majorization-Minimization for Nonnegative Matrix Factorization with the β-divergence](https://mlsanity.com/paper/2106.15214/) (2021)
- [Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates](https://mlsanity.com/paper/2201.01652/) (2022)
- [Stochastic gradient descent estimation of generalized matrix factorization models with application to single-cell RNA sequencing data](https://mlsanity.com/paper/2412.20509/) (2024)
- [Revisiting Incremental Stochastic Majorization-Minimization Algorithms with Applications to Mixture of Experts](https://mlsanity.com/paper/2601.19811/) (2026)
- [Learning fMRI activations dictionaries across individual geometries via optimal transport](https://mlsanity.com/paper/2605.20883/) (2026)

## Abstract (arXiv)

We present a matrix-factorization algorithm that scales to input matrices with both huge number of rows and columns. Learned factors may be sparse or dense and/or non-negative, which makes our algorithm suitable for dictionary learning, sparse component analysis, and non-negative matrix factorization. Our algorithm streams matrix columns while subsampling them to iteratively learn the matrix factors. At each iteration, the row dimension of a new sample is reduced by subsampling, resulting in lower time complexity compared to a simple streaming algorithm. Our method comes with convergence guarantees to reach a stationary point of the matrix-factorization problem. We demonstrate its efficiency on massive functional Magnetic Resonance Imaging data (2 TB), and on patches extracted from hyperspectral images (103 GB). For both problems, which involve different penalties on rows and columns, we obtain significant speed-ups compared to state-of-the-art algorithms.