2021/02/02 by Chen, Sitan, Song, Zhao, Tao, Runzhou +1
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.2102.01570
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× m, we want to find W∈\0,1\m× 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 = WW\top 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 = \widetildeΩ(r), which we do using tools from Littlewood-Offord theory and estimates for binary Krawtchouk polynomials.