Algorithms and Applications to Weighted Rank-one Binary Matrix Factorization

Haibing Lu, Xi Chen, Junmin Shi, Jaideep Vaidya, Vijayalakshmi Atluri, Yuan Hong, Wei Huang

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

Many applications use data that are better represented in the binary matrix form, such as click-stream data, market basket data, document-term data, user-permission data in access control, and others. Matrix factorization methods have been widely used tools for the analysis of high-dimensional data, as they automatically extract sparse and meaningful features from data vectors. However, existing matrix factorization methods do not work well for the binary data. One crucial limitation is interpretability, as many matrix factorization methods decompose an input matrix into matrices with fractional or even negative components, which are hard to interpret in many real settings. Some matrix factorization methods, like binary matrix factorization, do limit decomposed matrices to binary values. However, these models are not flexible to accommodate some data analysis tasks, like trading off summary size with quality and discriminating different types of approximation errors. To address those issues, this article presents weighted rank-one binary matrix factorization, which is to approximate a binary matrix by the product of two binary vectors, with parameters controlling different types of approximation errors. By systematically running weighted rank-one binary matrix factorization, one can effectively perform various binary data analysis tasks, like compression, clustering, and pattern discovery. Theoretical properties on weighted rank-one binary matrix factorization are investigated and its connection to problems in other research domains are examined. As weighted rank-one binary matrix factorization in general is NP-hard, efficient and effective algorithms are presented. Extensive studies on applications of weighted rank-one binary matrix factorization are also conducted.

Original languageEnglish (US)
Article number3386599
JournalACM Transactions on Management Information Systems
Volume11
Issue number2
DOIs
StatePublished - Jul 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Management Information Systems
  • General Computer Science

Keywords

  • Discrete data
  • clustering
  • compression
  • pattern discovery

Fingerprint

Dive into the research topics of 'Algorithms and Applications to Weighted Rank-one Binary Matrix Factorization'. Together they form a unique fingerprint.

Cite this