Kueng, Richard and Tropp, Joel A. (2019) Binary Component Decomposition. Part I: The Positive-Semidefinite Case. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20201218-154441081
![]() |
PDF
- Submitted Version
See Usage Policy. 531kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20201218-154441081
Abstract
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: |
| ||||||||||
ORCID: |
| ||||||||||
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. | ||||||||||
Funders: |
| ||||||||||
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: | https://resolver.caltech.edu/CaltechAUTHORS:20201218-154441081 | ||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||
ID Code: | 107223 | ||||||||||
Collection: | CaltechAUTHORS | ||||||||||
Deposited By: | George Porter | ||||||||||
Deposited On: | 21 Dec 2020 15:33 | ||||||||||
Last Modified: | 21 Dec 2020 15:33 |
Repository Staff Only: item control page