Approximation method to rank-one binary matrix factorization

In this paper, we study the rank-one binary matrix factorization problem, which plays a key role in analyzing the high dimensional discrete-attributed datasets. We first transform this problem into an equivalent binary quadratic programming, and then a mixed-integer linear formulation is obtained using linearization technique. A characterization on the extreme points is given for the polyhedron of the linearized formulation. To the best of our knowledge, this is the first time to study the extreme points property of the rank-one binary matrix factorization. Based on this property, a LP rounding based 2-approximation algorithm is designed for this problem. Numerical results illustrate the efficiency of the proposed approximation algorithm.