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.

Authors

• Florent Avellaneda Université du Québec à Montréal Centre de Recherche de l’Institut Universitaire de Gériatrie de Montréal
• Roger Villemaire Université du Québec à Montréal

Keywords

No keywords are indexed for this paper.