Sparse Boolean Matrix Factorizations

Miettinen, Pauli

doi:10.1109/ICDM.2010.93

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Sparse Boolean Matrix Factorizations

MPS-Authors

/persons/resource/persons45046

Miettinen, Pauli
Databases and Information Systems, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Miettinen, P. (2010). Sparse Boolean Matrix Factorizations. In G. I. Webb, B. Liu, C. Zhang, D. Gunopulos, & X. Wu (Eds.), 10th IEEE International Conference on Data Mining (pp. 935-940). Los Alamitos, CA: IEEE Computer Society.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-1532-2

Abstract

Matrix factorizations are commonly used methods in data mining. When the input data is Boolean, replacing the standard matrix multiplication with Boolean matrix multiplication can yield more intuitive results. Unfortunately, finding a good Boolean decomposition is known to be computationally hard, with even many sub-problems being hard to approximate. Many real-world data sets are sparse, and it is often required that also the factor matrices are sparse. This requirement has motivated many new matrix decomposition methods and many modifications of the existing methods. This paper studies how Boolean matrix factorizations behave with sparse data: can we assume some sparsity on the factor matrices, and does the sparsity help with the computationally hard problems. The answer to these problems is shown to be positive.