From-Below Approximations in Boolean Matrix Factorization: Geometry and New Algorithm
This work addresses matrix factorization challenges in data analysis, offering incremental improvements for applications like data mining and pattern recognition.
The paper tackles the problem of Boolean matrix factorization by introducing a new algorithm that focuses on from-below approximations to prioritize significant matrix entries, resulting in improved performance with good coverage by the first k factors and a smaller number of factors needed for exact decomposition compared to existing methods.
We present new results on Boolean matrix factorization and a new algorithm based on these results. The results emphasize the significance of factorizations that provide from-below approximations of the input matrix. While the previously proposed algorithms do not consider the possibly different significance of different matrix entries, our results help measure such significance and suggest where to focus when computing factors. An experimental evaluation of the new algorithm on both synthetic and real data demonstrates its good performance in terms of good coverage by the first k factors as well as a small number of factors needed for exact decomposition and indicates that the algorithm outperforms the available ones in these terms. We also propose future research topics.