Low-Rank Boolean Matrix Approximation by Integer Programming
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.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningDimensionality ReductionregressionSimilar Papers 제목 키워드 기반
Algorithms for Boolean Matrix Factorization using Integer Programming and Heuristics
Boolean matrix factorization (BMF) approximates a given binary input matrix as the product of two smaller binary factors. Unlike binary matrix factorization based on standard arithmetic, BMF employs the Boolean OR and AN…
Binary Matrix Factorisation and Completion via Integer Programming
Binary matrix factorisation is an essential tool for identifying discrete patterns in binary data. In this paper we consider the rank-k binary matrix factorisation problem (k-BMF) under Boolean arithmetic: we are given a…
Algorithms for Boolean Matrix Factorization using Integer Programming
Boolean matrix factorization (BMF) approximates a given binary input matrix as the product of two smaller binary factors. As opposed to binary matrix factorization which uses standard arithmetic, BMF uses the Boolean OR …
Boolean and $\mathbb{F}_p$-Matrix Factorization: From Theory to Practice
Boolean Matrix Factorization (BMF) aims to find an approximation of a given binary matrix as the Boolean product of two low-rank binary matrices. Binary data is ubiquitous in many fields, and representing data by binary …
Approximation Schemes for Low-Rank Binary Matrix Approximation Problems
We provide a randomized linear time approximation scheme for a generic problem about clustering of binary vectors subject to additional constrains. The new constrained clustering problem encompasses a number of problems …
ClusteringConstrained ClusteringLEMMA