# Binary Component Decomposition Part I: The Positive-Semidefinite Case

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2019.

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

- [Bounded Simplex-Structured Matrix Factorization: Algorithms, Identifiability and Applications](https://mlsanity.com/paper/2209.12638/) (2022)
- [Symmetric Sparse Boolean Matrix Factorization and Applications](https://mlsanity.com/paper/2102.01570/) (2021)
- [Fast and Low-Memory Deep Neural Networks Using Binary Matrix Factorization](https://mlsanity.com/paper/2210.13468/) (2022)
- [Empirical Bayes Covariance Decomposition, and a Solution to the Multiple Tuning Problem in Sparse PCA](https://mlsanity.com/paper/2312.03274/) (2023)
- [On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization](https://mlsanity.com/paper/2607.04875/) (2026)

## Abstract (arXiv)

This paper studies the problem of decomposing a low-rank positive-semidefinite matrix into symmetric factors with binary entries, either ± 1 or 0,1. This research answers fundamental questions about the existence and uniqueness of these decompositions. It also leads to tractable factorization algorithms that succeed under a mild deterministic condition. A companion paper addresses the related problem of decomposing a low-rank rectangular matrix into a binary factor and an unconstrained factor.