Boolean Matrix Tri-Factorization

Abstract

Matrix tri-factorizations (MTFs) aim to decompose an input matrix X into the product of three factor matrices, instead of only two as in standard matrix factorization (MF). In contrast to MF, MTF is able to cluster both rows and columns of X while quantifying the relationship among these two groups of clusters. When dealing with binary input matrices, Boolean matrix factorization (BMF) is a natural extension of MF. In this work we focus on Boolean matrix tri-factorization (BMTF) that extends BMF to the tri-factorization framework. We first show an identifiability result for BMTF, namely, we show that the factors are unique under certain sparsity conditions. Then we propose an algorithm to compute the factors of BMTF, and perform numerical experiments to show how it performs on synthetic and real data.