Binary Matrix Factorization Discretization

Binary Matrix Factorization can be used at the core of many data analysis pipelines. It is used for clustering items, categorical characteristics of observations, and recommendation systems for users interacting with itemsets. The most common algorithms approximate the factorization through gradient descent. However, the results are approximately binary. When thresholded, the reconstruction error is so high that the matrices are no longer representative of the original. Therefore, the analyst must always choose between precision and explainability. We achieved theoretical results that greatly improve solving the exact subproblem of this factorization. These results enable a backtracking approach that can solve the linearized formulation of the subproblem in large binary matrices taking advantage of their sparsity in real settings. Finally, we test this new approach post-processing matrices yielded by gradient descent algorithms using the new backtracking to obtain actually binary factorized matrices with a diminished reconstruction error, close the level of what gradient descent is capable of finding. We tested our algorithm using gene expression datasets, and could find a error rate comparable to the relaxed continuous problem before discretization. The discretized matrices allow for domain experts to question biclusters of gene-expressions and samples taken.