From-below approximations in Boolean matrix factorization: Geometry and new algorithm

Abstract 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 few factors as well as a small number of factors needed for an almost exact decomposition and indicates that the algorithm outperforms the available ones in these terms. We also propose future research topics.

• Publication year

  2013

• Venue

  Journal of computer and system sciences (Print)

• Publication date

  2013-06-20

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.jcss.2015.06.002.arXiv 1306.4905
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Combinatorial Matrix Theory

  2013cited by this paper
• Ordinal Factor Analysis

  2012cited by this paper
• Comparing apples and oranges: measuring differences between exploratory data mining results

  2012cited by this paper
• Constraint-Aware Role Mining via Extended Boolean Matrix Decomposition

  2012cited by this paper
• Optimal Factorization of Three-Way Binary Data Using Triadic Concepts

  2012cited by this paper
• Optimal decompositions of matrices with entries from residuated lattices

  2012cited by this paper
• On Finding Joint Subspace Boolean Matrix Factorizations

  2012cited by this paper
• Model order selection for boolean matrix factorization

  2011cited by this paper
• Boolean Tensor Factorizations

  2011cited by this paper
• Summarizing transactional databases with overlapped hyperrectangles

  2011cited by this paper
• Discovery of optimal factors in binary data via a novel method of matrix decomposition

  2010influential reference
• An Information-Theoretic Approach to Finding Informative Noisy Tiles in Binary Databases

  2010cited by this paper
• Mining Top-K Patterns from Binary Datasets in Presence of Noise

  2010cited by this paper
• Sparse Boolean Matrix Factorizations

  2010cited by this paper
• Boolean Factor Analysis for Data Preprocessing in Machine Learning

  2010cited by this paper
• Relational Mathematics

  2010cited by this paper
• Formal Concept Analysis

  2009influential reference
• The Boolean column and column-row matrix decompositions

  2008cited by this paper
• Fast exact and heuristic methods for role minimization problems

  2008influential reference
• Optimal Boolean Matrix Decomposition: Application to Role Engineering

  2008cited by this paper
• The role mining problem: finding a minimal descriptive set of roles

  2007cited by this paper
• The Discrete Basis Problem

  2006influential reference
• What is the Dimension of Your Binary Data?

  2006cited by this paper
• DNA copy number amplification profiling of human neoplasms

  2006influential reference
• Constraint-Based Mining of Fault-Tolerant Patterns from Boolean Data

  2005cited by this paper
• Tiling Databases

  2004influential reference
• Comparing performance of algorithms for generating concept lattices

  2002cited by this paper
• Formal Concept Analysis: Mathematical Foundations

  1998influential reference
• Introduction to lattices and order

  1990cited by this paper
• Boolean matrix theory and applications

  1982cited by this paper
• A mathematical analysis of human leukocyte antigen serology

  1978cited by this paper

• Independent subcontexts and blocks of concept lattices. Definitions and relationships to decompose fuzzy contexts

  2025cites this paper
• Reduce before you factorize: A simple scheme for Boolean matrix factorization

  2025cites this paper
• Data preprocessing using banded structure and image morphology enhancing Boolean matrix factorization

  2025cites this paper
• What is the intrinsic dimension of your binary data? - and how to compute it quickly

  2024cites this paper
• Delegation-Relegation for Boolean Matrix Factorization

  2024influential citation
• Factorizing formal contexts from closures of necessity operators

  2024cites this paper
• Binary data in matrices with singular value decomposition method

  2024cites this paper
• Semiconcept and concept representations

  2024cites this paper
• Semantic explorations in factorizing Boolean data via formal concepts

  2024cites this paper
• Revisiting data reduction for boolean matrix factorization algorithms based on formal concept analysis

  2024cites this paper
• The Discriminative Discrete Basis Problem: Definitions, Algorithms, Benchmarking, and Application to Brain's Functional Dynamics

  2023cites this paper
• Boolean matrix factorization for symmetric binary variables

  2023cites this paper
• Role Minimization Optimization Algorithm Based on Concept Lattice Factor

  2023influential citation
• Bias aware probabilistic Boolean matrix factorization

  2022cites this paper
• Boolean Matrix Factorization for Data with Symmetric Variables

  2022cites this paper
• Concept reduction in formal concept analysis based on representative concept matrix

  2022cites this paper
• Undercover Boolean Matrix Factorization with MaxSAT

  2022cites this paper
• Boolean matrix factorization with background knowledge

  2022cites this paper
• Revisiting the GreCon Algorithm for Boolean Matrix Factorization

  2022influential citation
• The 8M Algorithm from Today’s Perspective

  2021influential citation
• GC and Other Methods for Full and Partial Context Coverage

  2021cites this paper
• Conceptual Coverage Driven by Essential Concepts: A Formal Concept Analysis Approach

  2021influential citation
• Model order selection for approximate Boolean matrix factorization problem

  2021cites this paper
• Boolean Matrix Factorization via Nonnegative Auxiliary Optimization

  2021cites this paper
• Concept reduction and concept characteristics in formal concept analysis

  2020cites this paper
• Unsupervised Discovery Of Semantically Aware Communities With Tensor Kruskal Decomposition: A Case Study In Twitter

  2020cites this paper
• The Singular Value Decomposition over Completed Idempotent Semifields

  2020cites this paper
• An incremental algorithm for the role mining problem

  2020cites this paper
• A knowledge reduction approach for linguistic concept formal context

  2020cites this paper
• Generalized inverses of Boolean tensors via the Einstein product

  2020cites this paper
• Simple Structure in Boolean Matrix Factorization

  2020influential citation
• Recent Developments in Boolean Matrix Factorization

  2020cites this paper
• Parallelization of the GreConD Algorithm for Boolean Matrix Factorization

  2019cites this paper
• Parallel exploration of partial solutions in Boolean matrix factorization

  2019cites this paper
• From-below Boolean matrix factorization algorithm based on MDL

  2019influential citation
• Factorization of matrices with grades via essential entries

  2019influential citation
• topFiberM: Scalable and Efficient Boolean Matrix Factorization

  2019cites this paper
• Factorizing Boolean matrices using formal concepts and iterative usage of essential entries

  2019influential citation
• Noisy and Incomplete Boolean Matrix Factorizationvia Expectation Maximization

  2019influential citation
• A Study of Boolean Matrix Factorization Under Supervised Settings

  2019influential citation
• Concise Description of Telecom Service Use Through Concept Chains

  2019cites this paper
• XOR-Based Boolean Matrix Decomposition

  2019influential citation
• Boolean Matrix Decomposition for Label Space Dimension Reduction: Method, Framework and Applications

  2019cites this paper
• minimum description length in boolean matrix factorization

  2019influential citation
• Generalized Inverses of Boolean Tensors via Einstein Product

  2019cites this paper
• On stability of fuzzy formal concepts over randomized one-sided formal context

  2018cites this paper
• Identifying Dynamics of Brain Function Via Boolean Matrix Factorization

  2018cites this paper
• A new algorithm for Boolean matrix factorization which admits overcovering

  2018influential citation
• Using Boolean factors for the construction of an artificial neural networks

  2018cites this paper
• Running Boolean Matrix Factorization in Parallel

  2018influential citation
• Basic Level Concepts as a Means to Better Interpretability of Boolean Matrix Factors and Their Application to Clustering

  2018cites this paper
• MDL for FCA: Is There a Place for Background Knowledge?

  2018cites this paper
• Data Reduction for Boolean Matrix Factorization Algorithms Based on Formal Concept Analysis

  2018cites this paper
• Understanding Collaborative Filtering with Galois Connections

  2018cites this paper
• Can We Measure the Interpretability of Factors?

  2018influential citation
• Toward quality assessment of Boolean matrix factorizations

  2018influential citation
• A mathematical theory of making hard decisions: model selection and robustness of matrix factorization with binary constraints

  2018cites this paper
• Handling Noise in Boolean Matrix Factorization

  2017influential citation
• Turning Krimp into a Triclustering Technique on Sets of Attribute-Condition Pairs that Compress

  2017cites this paper
• Formal Concept Analysis of Social Networks

  2017influential citation
• An Overview of Label Space Dimension Reduction for Multi-Label Classification

  2017cites this paper
• Multimodal Clustering for Community Detection

  2017cites this paper
• Boolean Matrix Decomposition by Formal Concept Sampling

  2017influential citation
• Exact and approximate Boolean matrix decomposition with column-use condition

  2016influential citation
• Integrating grey sequencing with the genetic algorithm–immune algorithm to optimise touch panel cover glass polishing process parameter design

  2016cites this paper
• QualityCover: Efficient binary relation coverage guided by induced knowledge quality

  2016cites this paper
• What You Will Gain By Rounding: Theory and Algorithms for Rounding Rank

  2016cites this paper
• How to assess quality of BMF algorithms?

  2016influential citation
• Evaluating Association Rules in Boolean Matrix Factorization

  2016influential citation
• Decomposition of Boolean multi-relational data with graded relations

  2016cites this paper
• Improved algorithms for exact and approximate boolean matrix decomposition

  2015cites this paper
• An Algorithm for the Multi-Relational Boolean Factor Analysis based on Essential Elements

  2014influential citation
• Impact of Boolean factorization as preprocessing methods for classification of Boolean data

  2014cites this paper
• Computing minimal sets of descriptive conditions for binary data

  2014cites this paper
• Beyond Boolean Matrix Decompositions: Toward Factor Analysis and Dimensionality Reduction of Ordinal Data

  2013cites this paper