License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.46
URN: urn:nbn:de:0030-drops-156422
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15642/
Chen, Sitan ;
Song, Zhao ;
Tao, Runzhou ;
Zhang, Ruizhe
Symmetric Sparse Boolean Matrix Factorization and Applications
Abstract
In this work, we study a variant of nonnegative matrix factorization where we wish to find a symmetric factorization of a given input matrix into a sparse, Boolean matrix. Formally speaking, given {?} ∈ {ℤ}^{m× m}, we want to find {?} ∈ {0,1}^{m× r} such that ‖ {?} - {?} {?}^⊤ ‖₀ is minimized among all {?} for which each row is k-sparse. This question turns out to be closely related to a number of questions like recovering a hypergraph from its line graph, as well as reconstruction attacks for private neural network training.
As this problem is hard in the worst-case, we study a natural average-case variant that arises in the context of these reconstruction attacks: {?} = {?} {?}^{⊤} for {?} a random Boolean matrix with k-sparse rows, and the goal is to recover {?} up to column permutation. Equivalently, this can be thought of as recovering a uniformly random k-uniform hypergraph from its line graph.
Our main result is a polynomial-time algorithm for this problem based on bootstrapping higher-order information about {?} and then decomposing an appropriate tensor. The key ingredient in our analysis, which may be of independent interest, is to show that such a matrix {?} has full column rank with high probability as soon as m = Ω̃(r), which we do using tools from Littlewood-Offord theory and estimates for binary Krawtchouk polynomials.
BibTeX - Entry
@InProceedings{chen_et_al:LIPIcs.ITCS.2022.46,
author = {Chen, Sitan and Song, Zhao and Tao, Runzhou and Zhang, Ruizhe},
title = {{Symmetric Sparse Boolean Matrix Factorization and Applications}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {46:1--46:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15642},
URN = {urn:nbn:de:0030-drops-156422},
doi = {10.4230/LIPIcs.ITCS.2022.46},
annote = {Keywords: Matrix factorization, tensors, random matrices, average-case complexity}
}
|
Keywords: |
|
Matrix factorization, tensors, random matrices, average-case complexity |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
