TY - JOUR
AU - Avellaneda, Florent
AU - Villemaire, Roger
PY - 2022/06/28
Y2 - 2024/08/14
TI - Undercover Boolean Matrix Factorization with MaxSAT
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 36
IS - 4
SE - AAAI Technical Track on Constraint Satisfaction and Optimization
DO - 10.1609/aaai.v36i4.20280
UR - https://ojs.aaai.org/index.php/AAAI/article/view/20280
SP - 3672-3681
AB - 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 “block-optimal” 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 “block-optimal” k-undercover algorithm outperforms the state-of-the-art even when compared with algorithms for the more general k-undercover Boolean Matrix Factorization problem for which only minimizing reconstruction error is required.
ER -