Projected Hierarchical ALS for Generalized Boolean Matrix Factorization

Abstract

We introduce a versatile approach for Boolean factorization of binary data matrices based on a projected hierarchical alternating least squares method. The general model considered in this work allows for an arbitrary Boolean combination of the binary rank-1 terms. The underlying approximation problem is tackled by relaxing the binary constraints and representing the combining function by a multivariate polynomial. This leads to closed-form and simple to implement updates of the alternating algorithm. Performance comparisons with other methods from the literature are presented for the standard Boolean (‘OR’) mixture model. We also pro-vide results on real data, as well as factorization examples using XOR and 3-term majority logical operators as combining functions.