hide
Free keywords:
-
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.
