Binary Component Decomposition Part I: The Positive-Semidefinite Case
| Autor: | Joel A. Tropp, Richard Kueng |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Semidefinite programming 52A20 15B48 (Primary) 15A21 52B12 90C27 (Secondary) Binary number Metric Geometry (math.MG) Mathematics - Statistics Theory Statistics Theory (math.ST) Positive-definite matrix Matrix decomposition Combinatorics Matrix (mathematics) Mathematics - Metric Geometry Factorization Optimization and Control (math.OC) Computer Science - Data Structures and Algorithms FOS: Mathematics Decomposition (computer science) Data Structures and Algorithms (cs.DS) Uniqueness Mathematics - Optimization and Control Mathematics |
| Zdroj: | SIAM Journal on Mathematics of Data Science. 3:544-572 |
| ISSN: | 2577-0187 |
| Popis: | This paper studies the problem of decomposing a low-rank positive-semidefinite matrix into symmetric factors with binary entries, either $\{\pm 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. 21(+4) pages, 3 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|