Binary Matrix Factorization and Consensus Algorithms

In data mining, SVD is a popular method that has been used for compressing high dimensional data. Binary matrix factorization (BMF) is a variant of SVD. There are two methods for binary factorization compression: the iterative heuristic and greedy algorithms. However, both of them are not perfect in applications. The iterative heuristic does not guarantee the convergence in most cases and greedy algorithms can´t fit the need of large-scale matrices factorization. In this paper a new method is used for BMF: consensus algorithms. Consensus algorithms are a brand-new approach to enumerating all the maximal bicliques for a given graph, which is proved to be an NP-complete problem and can give the solution in incremental polynomial time. For some bipartite graphs, the time complexity is polynomial. Experiments show that when the iterative heuristic does not work, consensus algorithm improves far more badly the efficiency than greedy algorithms, and ensures the stability.