Low rank approximation of binary matrices: Column subset selection and generalizations

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review



  • Chen Dan, Carnegie Mellon University
  • ,
  • Kristoffer Arnsfelt Hansen
  • He Jiang, University of Southern California
  • ,
  • Liwei Wang, Peking University
  • ,
  • Yuchen Zhou, University of Wisconsin-Madison

Low rank approximation of matrices is an important tool in machine learning. Given a data matrix, low rank approximation helps to find factors, patterns, and provides concise representations for the data. Research on low rank approximation usually focuses on real matrices. However, in many applications data are binary (categorical) rather than continuous. This leads to the problem of low rank approximation of binary matrices. Here we are given a d × n binary matrix A and a small integer k < d. The goal is to find two binary matrices U and V of sizes d × k and k × n respectively, so that the Frobenius norm of A − UV is minimized. There are two models of this problem, depending on the definition of the dot product of binary vectors: The GF(2) model and the Boolean semiring model. Unlike low rank approximation of a real matrix which can be efficiently solved by Singular Value Decomposition, we show that approximation of a binary matrix is NP-hard, even for k = 1. In this paper, our main concern is the problem of Column Subset Selection (CSS), in which the low rank matrix U must be formed by k columns of the data matrix, and we are interested in the approximation ratio achievable by CSS for binary matrices. For the GF(2) model, we show that CSS has approximation ratio bounded by k 2 + 1 + 2(2k k −1) and this is asymptotically tight. For the Boolean model, it turns out that CSS is no longer sufficient to obtain a bound. We then develop a Generalized CSS (GCSS) procedure in which the columns of U are generated from Boolean formulas operating bitwise on selected columns of the data matrix. We show that the approximation ratio achieved by GCSS is bounded by 2k−1 + 1, and argue that an exponential dependency on k is seems inherent.

Original languageEnglish
Title of host publication43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
EditorsIgor Potapov, James Worrell, Paul Spirakis
Number of pages16
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication year2018
Article number41
ISBN (print)9783959770866
Publication statusPublished - 2018
Event43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 - Liverpool, United Kingdom
Duration: 27 Aug 201831 Aug 2018


Conference43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
LandUnited Kingdom
SeriesLeibniz International Proceedings in Informatics

    Research areas

  • Approximation algorithms, Binary matrices, Low rank approximation

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 134881022