2026-08-07T04:49:19Z
https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:15642
2024-03-06T10:55:50Z
ddc:004
open_access
Symmetric Sparse Boolean Matrix Factorization and Applications
Chen, Sitan
Song, Zhao
Tao, Runzhou
Zhang, Ruizhe
Matrix factorization
tensors
random matrices
average-case complexity
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.
Schloss Dagstuhl β Leibniz-Zentrum fΓΌr Informatik
Sitan Chen and Zhao Song and Runzhou Tao and Ruizhe Zhang
2022
Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
InProceedings
Text
doc-type:ResearchArticle
publishedVersion
application/pdf
doi:10.4230/LIPIcs.ITCS.2022.46
urn:nbn:de:0030-drops-156422
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.46
eng
https://creativecommons.org/licenses/by/4.0/legalcode