document: Mining discrete patterns via binary matrix factorization Mining discrete patterns in binary data is important for subsampling , compression , and clustering . We consider rank-one binary matrix approximations that identify the dominant patterns of the data , while preserving its discrete property . A best approximation on such data has a minimum set of inconsistent entries , i.e. , mismatches between the given binary data and the approximate matrix . Due to the hardness of the problem , previous accounts of such problems employ heuristics and the resulting approximation may be far away from the optimal one . In this paper , we show that the rank-one binary matrix approximation can be reformulated as a 0-1 integer linear program ( ILP ) . However , the ILP formulation is computationally expensive even for small-size matrices . We propose a linear program ( LP ) relaxation , which is shown to achieve a guaranteed approximation error bound . We further extend the proposed formulations using the regularization technique , which is commonly employed to address overfitting . The LP formulation is restricted to medium-size matrices , due to the large number of variables involved for large matrices . Interestingly , we show that the proposed approximate formulation can be transformed into an instance of the minimum s-t cut problem , which can be solved efficiently by finding maximum flows . Our empirical study shows the efficiency of the proposed algorithm based on the maximum flow . Results also confirm the established theoretical bounds .
doc_bio_tags: O O O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O