Binary Component Decomposition Part I: The Positive-Semidefinite Case

Richard Küng; Joel A. Tropp

doi:10.1137/19M1278612

Binary Component Decomposition Part I: The Positive-Semidefinite Case

Richard Küng, Joel A. Tropp

Department of Integrated Circuits and System Design

Research output: Contribution to journal › Article › peer-review

Abstract

This paper studies the problem of decomposing a low-rank positive-semidefinite matrix into symmetric factors with binary entries, either {+1,-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.

Original language	English
Pages (from-to)	544-572
Number of pages	28
Journal	SIAM Journal on Mathematics of Data Science
Volume	3
Issue number	2
DOIs	https://doi.org/10.1137/19M1278612
Publication status	Published - 2021

Fields of science

102 Computer Sciences
202 Electrical Engineering, Electronics, Information Engineering

JKU Focus areas

Digital Transformation

Access to Document

10.1137/19M1278612

Cite this

@article{76fcaa842188490ebbfb8d089c6f1349,

title = "Binary Component Decomposition Part I: The Positive-Semidefinite Case",

abstract = "This paper studies the problem of decomposing a low-rank positive-semidefinite matrix into symmetric factors with binary entries, either {+1,-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.",

author = "Richard K{\"u}ng and Tropp, {Joel A.}",

year = "2021",

doi = "10.1137/19M1278612",

language = "English",

volume = "3",

pages = "544--572",

journal = "SIAM Journal on Mathematics of Data Science",

issn = "2577-0187",

number = "2",

}

TY - JOUR

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

AU - Küng, Richard

AU - Tropp, Joel A.

PY - 2021

Y1 - 2021

N2 - This paper studies the problem of decomposing a low-rank positive-semidefinite matrix into symmetric factors with binary entries, either {+1,-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.

AB - This paper studies the problem of decomposing a low-rank positive-semidefinite matrix into symmetric factors with binary entries, either {+1,-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.

U2 - 10.1137/19M1278612

DO - 10.1137/19M1278612

M3 - Article

SN - 2577-0187

VL - 3

SP - 544

EP - 572

JO - SIAM Journal on Mathematics of Data Science

JF - SIAM Journal on Mathematics of Data Science

IS - 2

ER -