Abstract
This paper introduces a new Boolean Matrix Factorization (BMF) algorithm based on the Rice-Siff agglomerative clustering method. Our approach, Rice-Siff Factorization (RSF), integrates a greedy set-cover framework, where formal concepts serve as interpretable factors, with a dynamic candidate-generation process. By incorporating optimized variants such as RSF with Early Stopping (RSF-ES), we propose a pruning criterion based on order-theoretic properties to detect redundant candidates and significantly enhance factor extraction. Extensive synthetic benchmarks and experiments on real-world datasets demonstrate the effectiveness and robustness of the proposed framework, showing that RSF-ES provides significant scalability gains, yielding speedups on high-dimensional datasets with thousands of attributes while maintaining mathematical exactness. A comprehensive comparison with established factorization algorithms and an analysis of its theoretical properties show that RSF-ES represents a highly efficient and scalable solution for Boolean data analysis.
Funding
VALID: Verifiable Algebraic and Logic tools for Imperfect Data
Citation
L. Antoni, D. Kotlárová, O. Krídlo, et al. “Effective greedy Boolean matrix factorization via the Rice-Siff algorithm”. In: International Journal of Approximate Reasoning 197 (2026), p. 109747. ISSN: 0888-613X. DOI: https://doi.org/10.1016/j.ijar.2026.109747. URL: https://www.sciencedirect.com/science/article/pii/S0888613X26001222.