Low-Rank Boolean Matrix Approximation by Integer Programming
This addresses a dimensionality reduction challenge for categorical data in ML, but appears incremental as it builds on existing low-rank approximation methods with a new computational approach.
The paper tackles the problem of finding low-rank approximations for Boolean matrices, which is relevant for categorical variables in machine learning, by proposing the first integer programming formulation with polynomial variables and constraints and reporting computational results on synthetic and real-world data.
Low-rank approximations of data matrices are an important dimensionality reduction tool in machine learning and regression analysis. We consider the case of categorical variables, where it can be formulated as the problem of finding low-rank approximations to Boolean matrices. In this paper we give what is to the best of our knowledge the first integer programming formulation that relies on only polynomially many variables and constraints, we discuss how to solve it computationally and report numerical tests on synthetic and real-world data.