The Discrete Basis Problem

By Pauli Miettinen, Taneli Mielikäinen, Aristides Gionis, Gautam Das, Heikki Mannila. IEEE Transactions on Knowledge and Data Engineering, 2006

329 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/e720b8b8494b2ea1bc8ecf5841050e0f1fdd84db

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Miguel L'azaro-Gredilla
2. Jaideep Vaidya
3. Blaise Thomson
4. Ulrich Paquet
5. Ole Winther
6. Jimeng Sun
7. R. Vuduc
8. Evangelos E. Papalexakis

In Computer Networks and Communications

1. Jaideep Vaidya
2. Blaise Thomson
3. Ulrich Paquet
4. Ole Winther
5. Jimeng Sun
6. R. Vuduc
7. Evangelos E. Papalexakis

In Signal Processing

1. Blaise Thomson
2. Ulrich Paquet
3. Ole Winther
4. Jimeng Sun
5. R. Vuduc
6. Evangelos E. Papalexakis
7. Walter F. Stewart
8. Dileep George

Citations in the corpus

• Discovery of optimal factors in binary data via a novel method of matrix decomposition (2010, neutral): “Note that this result is also reported in [22,31] where the authors were apparently not familiar with [23,24].”
• Hierarchical compositional feature learning (2016, background): “In (Ravanbakhsh et al., 2015) it is shown that max-product message passing (MPMP) produces state-of-the-art results for the BMF problem, improving even on the performance of the Asso heuristic.”
• The role mining problem: finding a minimal descriptive set of roles (2007, background): “Without semantics (i.e., human expert knowledge), minimality serves as a best approximation for realizing good descriptive roles.”
• SUSTain: Scalable Unsupervised Scoring for Tensors and its Application to Phenotyping (2018, background): “ect application of this approach would introduce negative values into the factors, thus hurting interpretability for nonnegative input. Finally, several prior works target binary factorization (e.g., [26, 41, 34, 30, 29, 28]). In contrast to strictly binary factors, SUSTain captures the quantity emb”
• On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation (2015, neutral): “}-matrices. Corollary 3. Rank-one ℓ 0-LRA, that is, problem (1.3) with r = 1, is NP-hard. Corollary 4. Rank-one BMF is NP-hard. Remark 1 (The discrete basis problem). The discrete basis problem (DSP) [26] is similar to BMF and can be formulated a follows: given a binary matrix M ∈ {0,1}m×n and a ran”
• A hierarchical model for ordinal matrix factorization (2011, background): “The extra constraints, however, result in the NP-hard discrete basis problem (Miettinen et al. 2008).”