The DOI matches its Crossref record; 34 of the 34 references it cites were found in a registry or an index.
The Discrete Basis Problem
Abstract
Matrix decomposition methods represent a data matrix as a product of two factor matrices: one containing basis vectors that represent meaningful concepts in the data, and another describing how the observed data can be expressed as combinations of the basis vectors. Decomposition methods have been studied extensively, but many methods return real-valued matrices. Interpreting real-valued factor matrices is hard if the original data is Boolean. In this paper, we describe a matrix decomposition formulation for Boolean data, the Discrete Basis Problem. The problem seeks for a Boolean decomposition of a binary matrix, thus allowing the user to easily interpret the basis vectors. We also describe a variation of the problem, the Discrete Basis Partitioning Problem. We show that both problems are NP-hard. For the Discrete Basis Problem, we give a simple greedy algorithm for solving it; for the Discrete Basis Partitioning Problem we show how it can be solved using existing methods. We present experimental results for the greedy algorithm and compare it against other, well known methods. Our algorithm gives intuitive basis vectors, but its reconstruction error is usually larger than with the real-valued methods. We discuss about the reasons for this behavior.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
(2003) · Journal of Machine Learning Research · doi:10.5555/944919.944937 · Cited by 32,337
Mining association rules between sets of items in large databases
Agrawal, R., Imieliński, T., & Swami, A. (1993) · Proceedings of the 1993 ACM SIGMOD international conference on Management of data · doi:10.1145/170035.170072 · Cited by 14,907
Learning the parts of objects by non-negative matrix factorization
Lee, D. D., & Seung, H. S. (1999) · Nature · doi:10.1038/44565 · Cited by 13,868
UCI Repository of machine learning databases
Blake, C. L. (1998) · Medical Entomology and Zoology · Cited by 10,582
ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION
Lee, D. D., & Seung, H. S. (2000) · Cited by 7,952
Paatero, P., & Tapper, U. (1994) · Environmetrics · doi:10.1002/env.3170050203 · Cited by 6,023
ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION
Seung, D., & Lee, L.-W. (2001) · Cited by 4,753
Probabilistic Latent Semantic Indexing
Hofmann, T. (2017) · ACM SIGIR Forum · doi:10.1145/3130348.3130370 · Cited by 3,988
Probabilistic latent semantic indexing
Hofmann, T. (1999) · Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/312624.312649 · Cited by 3,976
(2000) · CrossRef Listing of Deleted DOIs · doi:10.1162/jmlr.2003.3.4-5.993 · Cited by 3,024
Fellows, M. R. (2002) · Electronic Notes in Theoretical Computer Science · doi:10.1016/s1571-0661(04)00301-9 · Cited by 2,836
Downey, R. G., & Fellows, M. R. (1999) · Monographs in Computer Science · doi:10.1007/978-1-4612-0515-9 · Cited by 2,532
NewsWeeder: Learning to Filter Netnews
Lang, K. (1995) · Machine Learning Proceedings 1995 · doi:10.1016/b978-1-55860-377-6.50048-7 · Cited by 2,051
Biclustering algorithms for biological data analysis: a survey
Madeira, S. C., & Oliveira, A. L. (2004) · IEEE/ACM Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2004.2 · Cited by 2,049
Parameterized Complexity Theory
(2006) · Texts in Theoretical Computer Science. An EATCS Series · doi:10.1007/3-540-29953-x · Cited by 1,869
Algorithms and applications for approximate nonnegative matrix factorization
Berry, M. W., Browne, M., Langville, A. N., Pauca, V. P., & Plemmons, R. J. (2007) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2006.11.006 · Cited by 1,512
Direct Clustering of a Data Matrix
Hartigan, J. A. (1972) · Journal of the American Statistical Association · doi:10.1080/01621459.1972.10481214 · Cited by 1,165
UCI Repository of Machine Learning Database
Newman, D. J. (1998) · Medical Entomology and Zoology · Cited by 824
PARAMETERIZED COMPLEXITY THEORY
Niedermeier, R. (2006) · Invitation to Fixed-Parameter Algorithms · doi:10.1093/acprof:oso/9780198566076.003.0013 · Cited by 574
Relative-Error $CUR$ Matrix Decompositions
Drineas, P., Mahoney, M. W., & Muthukrishnan, S. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/07070471x · Cited by 461
Drineas, P., Kannan, R., & Mahoney, M. W. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704442702 · Cited by 310
A Generalized Maximum Entropy Approach to Bregman Co-clustering and Matrix Approximation
Banerjee, A., Dhillon, I. S., Ghosh, J., et al. (2004) · Cited by 303
The role mining problem: finding a minimal descriptive set of roles
Vaidya, J., Atluri, V., & Guo, Q. (2007) · Proceedings of the 12th ACM symposium on Access control models and technologies · doi:10.1145/1266840.1266870 · Cited by 281
Geerts, F., Goethals, B., & Mielikäinen, T. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30214-8_22 · Cited by 178
Variational Extensions to EM and Multinomial PCA
Buntine, W. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-36755-1_3 · Cited by 163
A generalized maximum entropy approach to bregman co-clustering and matrix approximation
Banerjee, A., Dhillon, I. S., Ghosh, J., Merugu, S., & Modha, D. S. (2004) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1014052.1014111 · Cited by 137
Buntine, W., & Jakulin, A. (2006) · Lecture notes in computer science · doi:10.1007/11752790_1 · Cited by 96
Compression, clustering, and pattern discovery in very high-dimensional discrete-attribute data sets
Koyutürk, M., Grama, A. Y., & Ramakrishnan, N. (2005) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2005.55 · Cited by 81
A New Conceptual Clustering Framework
Mishra, N., Ron, D., & Swaminathan, R. (2004) · Machine Learning · doi:10.1023/b:mach.0000033117.77257.41 · Cited by 69
Miettinen, P., Mielikäinen, T., Gionis, A., Das, G., & Mannila, H. (2006) · Lecture notes in computer science · doi:10.1007/11871637_33 · Cited by 40
Self-citationOn Finding Large Conjunctive Clusters
Mishra, N., Ron, D., & Swaminathan, R. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45167-9_33 · Cited by 30
The aspect Bernoulli model: multiple causes of presences and absences
Bingham, E., Kabán, A., & Fortelius, M. (2007) · Pattern Analysis and Applications · doi:10.1007/s10044-007-0096-4 · Cited by 29
Metadata
- Authors
- Miettinen, P., Mielikainen, T., Gionis, A., Das, G., & Mannila, H.
- Venue
- IEEE Transactions on Knowledge and Data Engineering
- Published
- 2008-10
- Volume
- 20
- Issue
- 10
- Pages
- 1348-1362
- ISSN
- 1041-4347 (ISSN-L)
- OpenAlex
- W2160342152
- Cited by
- 272
- References
- 34
- FWCI
- 14.80
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.