Factorization of Binary Matrices: Rank Relations, Uniqueness and Model Selection of Boolean Decomposition

The application of binary matrices are numerous. Representing a matrix as a mixture of a small collection of latent vectors via low-rank decomposition is often seen as an advantageous method to interpret and analyze data. In this work, we examine the factorizations of binary matrices using standard arithmetic (real and nonnegative) and logical operations (Boolean and Z(2)). We examine the relationships between the different ranks, and discuss when factorization is unique. In particular, we characterize when a Boolean factorization X = W Lambda H has a uniqueW, a unique H (for a fixedW), and when bothW and H are unique, given a rank constraint. We introduce a method for robust Boolean model selection, called BMFk, and show on numerical examples that BMFk not only accurately determines the correct number of Boolean latent features but reconstruct the pre-determined factors accurately.

Automated summary

This work examines the factorizations of binary matrices using standard arithmetic and logical operations, and discusses the uniqueness conditions of the factorization. The introduced method BMFk accurately determines the number of Boolean latent features and reconstructs the factors.