Nonnegative matrix factorization via rank-one downdate

ABSTRACT

Nonnegative matrix factorization (NMF) was popularized as a tool for data mining by Lee and Seung in 1999. NMF attempts to approximate a matrix with nonnegative entries by a product of two low-rank matrices, also with nonnegative entries. We propose an algorithm called rank-one downdate (R1D) for computing an NMF that is partly motivated by the singular value decomposition. This algorithm computes the dominant singular values and vectors of adaptively determined sub-matrices of a matrix. On each iteration, R1D extracts a rank-one submatrix from the original matrix according to an objective function. We establish a theoretical result that maximizing this objective function corresponds to correctly classifying articles in a nearly separable corpus. We also provide computational experiments showing the success of this method in identifying features in realistic datasets. The method is also much faster than other NMF routines.

REFERENCES

• 1: Asgarian, N., & Greiner, R. (2006). Using rank-1 biclusters to classify microarray data. Department of Computing Science, University of Alberta, Edmonton, AB, Canada.
• 2: Bergmann, S., Ihmels, J., & Barkai, N. (2003). Iterative signature algorithm for the analysis of largescale gene expression data. Physical Review E, 67, 031902.
• 3: Michael Biggs , Ali Ghodsi , Stephen Vavasis, Nonnegative matrix factorization via rank-one downdate, Proceedings of the 25th international conference on Machine learning, p.64-71, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390165]
• 4: C. Boutsidis , E. Gallopoulos, SVD based initialization: A head start for nonnegative matrix factorization, Pattern Recognition, v.41 n.4, p.1350-1362, April, 2008 [doi>10.1016/j.patcog.2007.09.010]
• 5: Cohen, J., & Rothblum, U. (1993). Nonnegative ranks, decompositions and factorizations of nonnegative matrices. Linear Algebra and its Applications, 190, 149--168.
• 6: Deerwester, S., Dumais, S., Furnas, G., Landauer, T., & Harshman, R. (1990). Indexing by latent semantic analysis. Journal of the American Society for Information Science, 41, 391--407.
• 7: Gillis, N. (2006). Approximation et sous-approximation de matrices par factorisation positive: algorithmes, complexité et applications. Master's thesis, Université Catholique de Louvain, Louvain-la-Neuve, Belgium. In French.
• 8: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 9: Gregory, D. A., & Pullman, N. J. (1983). Semiring rank: Boolean rank and nonnegative matrix rank. J. Combin. Inform. System Sci, 3, 223--233.
• 10: Hofmann, T. (1999). Probabilistic latent semantic analysis. UAI '99: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, Stockholm, Sweden, July 30-August 1, 1999 (pp. 289--296). Morgan Kaufmann.
• 11: Hoyer, P. (2000). nmfpack - matlab code for nmf. http://http://www.hiit.fi/node/70.
• 12: Patrik O. Hoyer, Non-negative Matrix Factorization with Sparseness Constraints, The Journal of Machine Learning Research, 5, p.1457-1469, 12/1/2004
• 13: Hyunsoo Kim , Haesun Park, Sparse non-negative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysis, Bioinformatics, v.23 n.12, p.1495-1502, June 2007 [doi>10.1093/bioinformatics/btm134]
• 14: Lee, D., & Seung, H. (1999). Learning the parts of objects by non-negative matrix factorization. Nature, 401, 788--791.
• 15: Paatero, P., & Tapper, U. (1994). Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. Environmetrics, 5, 111--126.
• 16: Christos H. Papadimitriou , Prabhakar Raghavan , Hisao Tamaki , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Journal of Computer and System Sciences, v.61 n.2, p.217-235, Oct. 2000 [doi>10.1006/jcss.2000.1711]
• 17: René Peeters, The maximum edge biclique problem is NP-complete, Discrete Applied Mathematics, v.131 n.3, p.651-654, 28 September 2003 [doi>10.1016/S0166-218X(03)00333-0]
• 18: G. W. Stewart, On the early history of the singular value decomposition, SIAM Review, v.35 n.4, p.551-566, Dec. 1993 [doi>10.1137/1035134]
• 19: TDT Study (1997). Topic detection and tracking pilot study. http://projects.ldc.upenn.edu/TDT/.
• 20: Vavasis, S. (2007). On the complexity of nonnegative matrix factorization. arxiv.org, 0708.4149.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields; Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Singular value decomposition

General Terms:
Algorithms, Design, Theory