mlsanityData to 7 Oct 2026

Symmetric Sparse Boolean Matrix Factorization and Applications

arXiv 2102.01570 ↗First posted 2 Feb 2021cs.LG cs.CR cs.DScited by 3

Not on the map. Why?

Abstract (arXiv)

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∈mathbbZm× m, we want to find W∈0,1m× r such that | M - WW^top |0 is minimized among all W 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: M = WWtop for W a random Boolean matrix with k-sparse rows, and the goal is to recover W 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 W 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 W has full column rank with high probability as soon as m = widetildeOmega(r), which we do using tools from Littlewood-Offord theory and estimates for binary Krawtchouk polynomials.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 18 of its 104 references that are in the map. First posted on arXiv 2 Feb 2021.

Builds on

18 of 104 references.

References · 18

  1. 2017mixup: Beyond Empirical Risk Minimizationcited by 5,155
  2. 2020InstaHide: Instance-hiding Schemes for Private Distributed Learningcited by 90
  3. 2017Relative Error Tensor Low Rank Approximationcited by 45
  4. 2020Is Private Learning Possible with Instance Encoding?cited by 22
  5. 2018Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorizationcited by 17
  6. 2020Recent Developments in Boolean Matrix Factorizationcited by 14
  7. 2015Boolean Matrix Factorization and Noisy Completion via Message Passingcited by 12
  8. 2015Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorizationcited by 7
  9. 2018Approximation Schemes for Low-Rank Binary Matrix Approximation Problemscited by 6
  10. 2019Binary Component Decomposition Part I: The Positive-Semidefinite Casecited by 5
  11. 2020On InstaHide, Phase Retrieval, and Sparse Matrix Factorizationcited by 4
  12. 2020InstaHide's Sample Complexity When Mixing Two Private Imagescited by 4
6 more
  1. 2017A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimalitycited by 3
  2. 2019Binary component decomposition Part II: The asymmetric casecited by 3
  3. 2013Exact Weight Subgraphs and the k-Sum Conjecturecited by 2
  4. 2018Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neuronscited by 2
  5. 2019Quartic First-Order Methods for Low-Rank Minimizationcited by 2
  6. 2013Overlapping Community Detection in Complex Networks using Symmetric Binary Matrix Factorizationcited by 1

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 2.

3 papers.

  1. 2022Dynamic Tensor Product Regressioncited by 17
  2. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  3. 2023Fast (1+varepsilon)-Approximation Algorithms for Binary Matrix Factorizationcited by 3