Interpretable nonnegative matrix decompositions

ABSTRACT

A matrix decomposition expresses a matrix as a product of at least two factor matrices. Equivalently, it expresses each column of the input matrix as a linear combination of the columns in the first factor matrix. The interpretability of the decompositions is a key issue in many data-analysis tasks. We propose two new matrix-decomposition problems: the nonnegative CX and nonnegative CUR problems, that give naturally interpretable factors. They extend the recently-proposed column and column-row based decompositions, and are aimed to be used with nonnegative matrices. Our decompositions represent the input matrix as a nonnegative linear combination of a subset of its columns (or columns and rows).

We present two algorithms to solve these problems and provide an extensive experimental evaluation where we assess the quality of our algorithms' results as well as the intuitiveness of nonnegative CX and CUR decompositions. We show that our algorithms return intuitive answers with smaller reconstruction errors than the previously-proposed methods for column and column-row decompositions.

REFERENCES

• 1: M. W. Berry et al. Algorithms and applications for approximate nonnegative matrix factorization. Computational Statistics & Data Analysis, 52(1):155--173, 2007.
• 2: Michael W. Berry , Shakhina A. Pulatova , G. W. Stewart, Algorithm 844: Computing sparse reduced-rank approximations to sparse matrices, ACM Transactions on Mathematical Software (TOMS), v.31 n.2, p.252-269, June 2005 [doi>10.1145/1067967.1067972]
• 3: A. ¸ Civril and M. Magdon-Ismail. Finding maximum volume sub-matrices of a matrix. Technical Report 07-08, Department of Computer Science, Rensselaer Polytechnic Institute, 2007.
• 4: S. C. Deerwester et al. Indexing by latent semantic analysis. J. of the American Society for Information Science, 41(6):391--407, 1990.
• 5: P. Drineas, M. W. Mahoney, and S. Muthukrishnan. Subspace sampling and relative-error matrix approximation: Column-based methods. In APPROX-RANDOM, pages 316--326, 2006.
• 6: Petros Drineas , Michael W. Mahoney , S. Muthukrishnan, Subspace sampling and relative-error matrix approximation: column-row-based methods, Proceedings of the 14th conference on Annual European Symposium, p.304-314, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_29]
• 7: P. Drineas, M. W. Mahoney, and S. Muthukrishnan. Relative-error CUR matrix decompositions, Aug. 2007. arXiv:0708.3696v1 {cs.DS}.
• 8: S. M. Embleton and E. S. Wheeler. Finnish dialect atlas for quantitative studies. J. of Quantitative Linguistics, 4(1-3):99--102, 1997.
• 9: S. M. Embleton and E. S. Wheeler. Computerized dialect atlas of Finnish: Dealing with ambiguity. J. of Quantitative Linguistics, 7(3):227--231, 2000.
• 10: Ken Goldberg , Theresa Roeder , Dhruv Gupta , Chris Perkins, Eigentaste: A Constant Time Collaborative Filtering Algorithm, Information Retrieval, v.4 n.2, p.133-151, July 2001 [doi>10.1023/A:1011419012209]
• 11: G. H. Golub and C. F. Van Loan. Matrix Computations. JHU Press, 1996.
• 12: M. K. Kozlov, S. P. Tarasov, and L. G. Hačijan. Polynomial solvability of convex quadratic programming. Soviet Math. Dokl., 20(5):1108--1111, 1979.
• 13: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

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

General Terms:
Algorithms, Experimentation

Keywords:
alternating least squares, column-row decompositions, local search, matrix decompositions