A Caltech Library Service

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

Kueng, Richard and Tropp, Joel A. (2019) Binary Component Decomposition. Part I: The Positive-Semidefinite Case. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Tropp, Joel A.0000-0003-1024-1791
Additional Information:Date: 31 July 2019. The authors thank Benjamin Recht for helpful conversations at an early stage of this project and Madeleine Udell for valuable comments regarding the related work section. Peter Jung suggested activity detection in massive MIMO system as a potential application. This research was partially funded by ONR awards N00014-11-1002, N00014-17-12146, and N00014-18-12363. Additional support was provided by the Gordon & Betty Moore Foundation.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-11-1002
Office of Naval Research (ONR)N00014-17-12146
Office of Naval Research (ONR)N00014-18-12363
Gordon and Betty Moore FoundationUNSPECIFIED
Subject Keywords:Matrix factorization, cut polytope, elliptope, semidefinite programming
Classification Code:2010 Mathematics Subject Classification. Primary: 52A20, 15B48. Secondary: 15A21, 52B12, 90C27
Record Number:CaltechAUTHORS:20201218-154441081
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:107223
Deposited By: George Porter
Deposited On:21 Dec 2020 15:33
Last Modified:21 Dec 2020 15:33

Repository Staff Only: item control page