# Matrix factorization with Binary Components

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

## Key facts

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

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

- [Gradient Disaggregation: Breaking Privacy in Federated Learning by Reconstructing the User Participant Matrix](https://mlsanity.com/paper/2106.06089/) (2021)
- [Support Recovery in Mixture Models with Sparse Parameters](https://mlsanity.com/paper/2202.11940/) (2022)
- [Spherical and Hyperbolic Toric Topology-Based Codes On Graph Embedding for Ising MRF Models: Classical and Quantum Topology Machine Learning](https://mlsanity.com/paper/2307.15778/) (2023)
- [Finding Rule-Interpretable Non-Negative Data Representation](https://mlsanity.com/paper/2206.01483/) (2022)
- [Binary Quadratic Quantization: Beyond First-Order Quantization for Real-Valued Matrix Compression](https://mlsanity.com/paper/2510.18650/) (2025)

## Abstract (arXiv)

Motivated by an application in computational biology, we consider low-rank matrix factorization with 0,1-constraints on one of the factors and optionally convex constraints on the second one. In addition to the non-convexity shared with other matrix factorization schemes, our problem is further complicated by a combinatorial constraint set of size 2m · r, where m is the dimension of the data points and r the rank of the factorization. Despite apparent intractability, we provide - in the line of recent work on non-negative matrix factorization by Arora et al. (2012) - an algorithm that provably recovers the underlying factorization in the exact case with O(m r 2r + mnr + r2 n) operations for n datapoints. To obtain this result, we use theory around the Littlewood-Offord lemma from combinatorics.