Undercover Boolean Matrix Factorization with MaxSAT

The k-undercover Boolean matrix factorization problem aims to approximate a m × n Boolean matrix X as the Boolean product of an m × k and a k × n matrices A • B such that X is a cover of A • B, i.e., no representation error is allowed on the 0's entries of the matrix X. To infer an optimal and "block-optimal" k-undercover, we propose two exact methods based on MaxSAT encodings. From a theoretical standpoint, we prove that our method of inferring "blockoptimal" k-undercover is a (1 -1 e ) ≈ 0.632 approximation for the optimal k-undercover problem. From a practical standpoint, experimental results indicate that our "blockoptimal" k-undercover algorithm outperforms the state-ofthe-art even when compared with algorithms for the more general k-undercover Boolean Matrix Factorization problem for which only minimizing reconstruction error is required.