ROBUST BINARY COMPONENT DECOMPOSITIONS

Semi-binary matrix factorization (semi-BMF) is a matrix de- composition model where the elements of one factor are bi- nary. Semi-BMF can be interpreted as a generalization of k- means, and can be employed in clustering problems such as community detection. In the absence of noise, Kueng and Tropp (SIAM J. Math. Data Sc., 2021) have recently pro- posed a provably correct algorithm for semi-BMF that require to solve semidefinite programs (SDPs). In this paper, we ex- tend their approach in the presence of noise. Moreover, since standard solvers for SDP rely on interior-point methods and do not scale well, we also propose a first-order method to re- duce the computational costs. We test our new algorithms on synthetic data, and show that they compare favorably with the state of the art.