Parameterized low-rank binary matrix approximation

Low-rank binary matrix approximation is a generic problem where one seeks a good approximation of a binary matrix by another binary matrix with some specific properties. A good approximation means that the difference between the two matrices in some matrix norm is small. The properties of the approximation binary matrix could be: a small number of different columns, a small binary rank or a small Boolean rank. Unfortunately, most variants of these problems are NP-hard. Due to this, we initiate the systematic algorithmic study of low-rank binary matrix approximation from the perspective of parameterized complexity. We show in which cases and under what conditions the problem is fixed-parameter tractable, admits a polynomial kernel and can be solved in parameterized subexponential time.

• Publication year

  2018

• Venue

  Data mining and knowledge discovery

• Publication date

  2018-03-16

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s10618-019-00669-5arXiv 1803.06102
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Review of Kernelization

  2020cited by this paper
• Non-negative Matrix Factorization

  2020cited by this paper
• Parameterized Algorithms

  2020influential reference
• A PTAS for 𝓁p-Low Rank Approximation

  2019cited by this paper
• Matrix Rigidity from the Viewpoint of Parameterized Complexity

  2018influential reference
• Approximation Schemes for Low-rank Binary Matrix Approximation Problems

  2018cited by this paper
• Ω-Lattices

  2017cited by this paper
• Approximation Algorithms for l0-Low Rank Approximation

  2017influential reference
• On the Parameterized Complexity of Biclique Cover and Partition

  2016influential reference
• Weighted low rank approximations with provable guarantees

  2016cited by this paper
• Computing approximate PSD factorizations

  2016cited by this paper
• Rank Reduction of Directed Graphs by Vertex and Edge Deletions

  2016cited by this paper
• A Survey of Role Mining

  2016cited by this paper
• Fast Biclustering by Dual Parameterization

  2015influential reference
• Generalized Independent Component Analysis Over Finite Alphabets

  2015cited by this paper
• Non-negative Matrix Factorization Techniques: Advances in Theory and Applications

  2015cited by this paper
• Reducing rank of the adjacency matrix by graph modification

  2015influential reference
• On Low Rank Approximation of Binary Matrices

  2015influential reference
• On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation

  2015cited by this paper
• Input Sparsity and Hardness for Robust Subspace Approximation

  2015cited by this paper
• Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters

  2014influential reference
• Low-Rank and Sparse Modeling for Visual Analysis

  2014cited by this paper
• Sketching as a Tool for Numerical Linear Algebra

  2014cited by this paper
• Approximation method to rank-one binary matrix factorization

  2014cited by this paper
• NP-hardness of hypercube 2-segmentation

  2014cited by this paper
• A Clustering Approach to Constrained Binary Matrix Factorization

  2014cited by this paper
• Monochromatic Bi-Clustering

  2013cited by this paper
• An Almost Optimal Algorithm for Computing Nonnegative Rank

  2013cited by this paper
• Mining Discrete Patterns via Binary Matrix Factorization

  2013cited by this paper
• Fundamentals of Parameterized Complexity

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

  2012cited by this paper
• Boolean Matrix Decomposition Problem: Theory, Variations and Applications to Data Engineering

  2012cited by this paper
• ICA over finite fields - Separability and algorithms

  2012cited by this paper
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization

  2011cited by this paper
• Outlier Detection for DNA Fragment Assembly

  2011cited by this paper
• Independent Component Analysis Over Galois Fields of Prime Order

  2011cited by this paper
• Weighted Rank-One Binary Matrix Factorization

  2011cited by this paper
• Computing a nonnegative matrix factorization -- provably

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

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

  2010cited by this paper
• Linear-time approximation schemes for clustering problems in any dimensions

  2010cited by this paper
• Optimal decompositions of matrices with grades into binary and graded matrices

  2010cited by this paper
• Robust principal component analysis?

  2009cited by this paper
• Data reduction and exact algorithms for clique cover

  2009cited by this paper
• Mining discrete patterns via binary matrix factorization

  2009cited by this paper
• Spectral Algorithms

  2009cited by this paper
• Complexity Lower Bounds using Linear Algebra

  2009cited by this paper
• On problems without polynomial kernels

  2009cited by this paper
• Rank-Sparsity Incoherence for Matrix Decomposition

  2009cited by this paper
• Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization

  2009cited by this paper
• Nonnegative Matrix and Tensor Factorizations - Applications to Exploratory Multi-way Data Analysis and Blind Source Separation

  2009cited by this paper
• Closest Substring Problems with Small Distances

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

  2008cited by this paper
• Surveys in Contemporary Mathematics: Rank and determinant functions for matrices over semirings

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

  2007cited by this paper
• The Discrete Basis Problem

  2006cited by this paper
• The Complexity of the Single Individual SNP Haplotyping Problem

  2005cited by this paper
• Tiling Databases

  2004cited by this paper
• Approximating extent measures of points

  2004influential reference
• Segmentation problems

  2004cited by this paper
• PROXIMUS: a framework for analyzing very high dimensional discrete-attributed datasets

  2003cited by this paper
• Approximate clustering via core-sets

  2002cited by this paper
• Polynomial-time approximation schemes for geometric min-sum median clustering

  2002cited by this paper
• Learning the parts of objects by non-negative matrix factorization

  1999cited by this paper
• On Two Segmentation Problems

  1999cited by this paper
• Color-coding

  1995cited by this paper
• Splitters and near-optimal derandomization

  1995cited by this paper
• Application of weighted Voronoi diagrams and randomization to variance-based k-clustering

  1994cited by this paper
• Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract)

  1994cited by this paper
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices

  1993cited by this paper
• Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices

  1991cited by this paper
• Expressing combinatorial optimization problems by linear programs

  1991cited by this paper
• Lattices, mobius functions and communications complexity

  1988cited by this paper
• On notions of information transfer in VLSI circuits

  1983cited by this paper
• Application of separability and independence notions for proving lower bounds of circuit complexity

  1980cited by this paper
• Contentment in graph theory: Covering graphs with cliques

  1977cited by this paper
• Graph-Theoretic Arguments in Low-Level Complexity

  1977cited by this paper
• Stat260/cs294: Randomized Algorithms for Matrices and Data

  year unknowncited by this paper

• Parameterized Complexity in Machine Learning

  2026cites this paper
• Algorithms for Boolean Matrix Factorization using Integer Programming and Heuristics

  2025cites this paper
• Low-Rank Binary Matrix Approximation Using SVD Based Clustering Technique: Detecting Autism Spectrum Disorder (ASD)

  2025cites this paper
• Matrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity

  2025influential citation
• Bi-objective Optimization in Role Mining

  2024influential citation
• On the parameterized complexity of clustering problems for incomplete data

  2023cites this paper
• A PTAS for ℓ0-Low Rank Approximation: Solving Dense CSPs over Reals

  2023cites this paper
• Column-coherent matrix decomposition

  2023cites this paper
• Structured Neural Networks for Density Estimation and Causal Inference

  2023cites this paper
• The Complexity of k-Means Clustering when Little is Known

  2022influential citation
• Boolean and $\mathbb{F}_{p}$-Matrix Factorization: From Theory to Practice

  2022cites this paper
• Generalized Noise Role Mining

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

  2021cites this paper
• Parameterized k-Clustering: Tractability Island

  2021cites this paper
• The Parameterized Complexity of Clustering Incomplete Data

  2021cites this paper
• Parameterized Complexity of Categorical Clustering with Size Constraints

  2021cites this paper
• DLRF-Net: A Progressive Deep Latent Low-Rank Fusion Network for Hierarchical Subspace Discovery

  2021cites this paper
• Parameterized Complexity of Feature Selection for Categorical Data Clustering

  2021influential citation
• Parameterized algorithms for identifying gene co-expression modules via weighted clique decomposition

  2021cites this paper
• Lossy Kernelization of Same-Size Clustering

  2021cites this paper
• On the Parameterized Complexity of Clustering Incomplete Data into Subspaces of Small Rank

  2020cites this paper
• Recent Developments in Boolean Matrix Factorization

  2020cites this paper
• Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation

  2020cites this paper
• Parameterized k-Clustering: The distance matters!

  2019cites this paper
• On Clustering Incomplete Data

  2019cites this paper
• Low-rank binary matrix approximation in column-sum norm

  2019cites this paper
• Low-Rank Approximation from Communication Complexity

  2019cites this paper
• Algorithmic Results for Clustering and Refined Physarum Analysis

  2018cites this paper
• Approximation Schemes for Low-rank Binary Matrix Approximation Problems

  2018cites this paper
• Parameterized Complexity of Feature Selection for Parameterized Complexity of Feature Selection for Categorical Data Clustering Categorical Data Clustering

  year unknowninfluential citation