Discovery of optimal factors in binary data via a novel method of matrix decomposition

By R. Belohlávek, Vilém Vychodil. Journal of computer and system sciences (Print), 2010

313 citations recorded by the source corpus.

We present a novel method of decomposition of an nxm binary matrix I into a Boolean product A@?B of an nxk binary matrix A and a kxm binary matrix B with k as small as possible. Attempts to solve this problem are known from Boolean factor analysis where I is interpreted as an object-attribute matrix, A and B are interpreted as object-factor and factor-attribute matrices, and the aim is to find a decomposition with a small number k of factors. The method presented here is based on a theorem proved in this paper. It says that optimal decompositions, i.e. those with the least number of factors possible, are those where factors are formal concepts in the sense of formal concept analysis. Finding an optimal decomposition is an NP-hard problem. However, we present an approximation algorithm for finding optimal decompositions which is based on the insight provided by the theorem. The algorithm avoids the need to compute all formal concepts and significantly outperforms a greedy approximation algorithm for a set covering problem to which the problem of matrix decomposition is easily shown to be reducible. We present results of several experiments with various data sets including those from CIA World Factbook and UCI Machine Learning Repository. In addition, we present further geometric insight including description of transformations between the space of attributes and the space of factors.

Subfields: Computational Theory and Mathematics, Management Science and Operations Research, Signal Processing

View Paper: https://www.semanticscholar.org/paper/64fde04682828a45ded49db53c9947f68748a3b0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Management Science and Operations Research

In Signal Processing

Citations in the corpus

List-decodable robust mean estimation and learning mixtures of spherical gaussians (2017, methodology): “2 of [RV17] or Corollary 3 of [VW04]: Lemma 4.”
DupLESS: Server-Aided Encryption for Deduplicated Storage (2013, background): “This has long been recognized by cryptographers [43], who typically aim to achieve security regardless of the distribution of the data.”
A classification of entanglement in three-qubit systems (2007, unknown): “17 80 v5 [ qu an tph ] 1 9 M ay 2 00 8”
A post-nonlinear mixture model approach to binary matrix factorization (2017, background): “…formulation: The direct BMF problem is to compute a binary matrix X ( X ij 2 { 0 , } of size ⇥ , given by two binary matrices W and H of respective sizes ( ) is called binary matrix product and is deﬁned as [10], [2]: ( W ik ^ H jk where ( ) and ( ) are OR and AND logical operators, respectively.”