Document Open Access Logo

On Restricted Nonnegative Matrix Factorization

Authors Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, James Worrell

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.103.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Dmitry Chistikov
Stefan Kiefer
Ines Marusic
Mahsa Shirmohammadi
James Worrell

Cite As Get BibTex

Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, and James Worrell. On Restricted Nonnegative Matrix Factorization. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 103:1-103:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.103

Abstract

Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative n*m matrix M into a product of a nonnegative n*d matrix W and a nonnegative d*m matrix H. Restricted NMF requires in addition that the column spaces of M and W coincide.

Finding the minimal inner dimension d is known to be NP-hard, both for NMF and restricted NMF. We show that restricted NMF is closely related to a question about the nature of minimal probabilistic automata, posed by Paz in his seminal 1971 textbook. We use this connection to answer Paz's question negatively, thus falsifying a positive answer claimed in 1974.

Furthermore, we investigate whether a rational matrix M always has a restricted NMF of minimal inner dimension whose factors W and H are also rational. We show that this holds for matrices M of rank at most 3 and we exhibit a rank-4 matrix for which W and H require irrational entries.

Subject Classification

Keywords
  • nonnegative matrix factorization
  • nonnegative rank
  • probabilistic automata
  • labelled Markov chains
  • minimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Aggarwal, H. Booth, J. O'Rourke, S. Suri, and C. K. Yap. Finding minimal convex nested polygons. Information and Computation, 83(1):98-110, 1989. Google Scholar
  2. S. Arora, R. Ge, R. Kannan, and A. Moitra. Computing a nonnegative matrix factorization - provably. In Proceedings of the 44th Symposium on Theory of Computing (STOC), pages 145-162, 2012. Google Scholar
  3. F. Bancilhon. A geometric model for stochastic automata. IEEE Trans. Computers, 23(12):1290-1299, 1974. Google Scholar
  4. M. W. Berry, N. Gillis, and F. Glineur. Document classification using nonnegative matrix factorization and underapproximation. In International Symposium on Circuits and Systems (ISCAS), pages 2782-2785. IEEE, 2009. Google Scholar
  5. S. S. Bucak and B. Günsel. Video content representation by incremental non-negative matrix factorization. In Proceedings of the International Conference on Image Processing (ICIP), pages 113-116. IEEE, 2007. Google Scholar
  6. J. Canny. Some algebraic and geometric computations in PSPACE. In Proceedings of the 20th Annual Symposium on Theory of Computing (STOC), pages 460-467, 1988. Google Scholar
  7. A. Cichocki, R. Zdunek, A. H. Phan, and S.-i. Amari. Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation. Wiley Publishing, 2009. Google Scholar
  8. J. E. Cohen and U. G. Rothblum. Nonnegative ranks, decompositions, and factorizations of nonnegative matrices. Linear Algebra and its Applications, 190:149-168, 1993. Google Scholar
  9. D. L. Donoho and V. Stodden. When does non-negative matrix factorization give a correct decomposition into parts? In Advances in Neural Information Processing Systems (NIPS), pages 1141-1148, 2003. Google Scholar
  10. N. Fijalkow, S. Kiefer, and M. Shirmohammadi. Trace refinement in labelled Markov decision processes. In Proceedings of the 19th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS), volume 9634 of Lecture Notes in Computer Science, pages 303-318. Springer, 2016. Google Scholar
  11. N. Gillis and F. Glineur. On the geometric interpretation of the nonnegative rank. Linear Algebra and its Applications, 437(11):2685-2712, 2012. Google Scholar
  12. N. Gillis and S. A. Vavasis. Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization. SIAM Journal on Optimization, 25(1):677-698, 2015. Google Scholar
  13. A. Kumar, V. Sindhwani, and P. Kambadur. Fast conical hull algorithms for near-separable non-negative matrix factorization. In Proceedings of the 30th International Conference on Machine Learning (ICML), page 231–239, 2013. Google Scholar
  14. D. D. Lee and H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755):788-791, 1999. Google Scholar
  15. A. Paz. Introduction to probabilistic automata. Academic Press, New York, 1971. Google Scholar
  16. J. Renegar. On the computational complexity and geometry of the first-order theory of the reals. Parts I-III. Journal of Symbolic Computation, 13(3):255-352, 1992. Google Scholar
  17. Y. Shitov. Nonnegative rank depends on the field. Technical report, arxiv.org, 2015. Available at ěrb|http://arxiv.org/abs/1505.01893|. Google Scholar
  18. D. Simanek. How to view 3D without glasses. https://www.lhup.edu/~dsimanek/3d/view3d.htm. Online, accessed in April 2016.
  19. E. Tjioe, M. W. Berry, and R. Homayouni. Discovering gene functional relationships using FAUN (feature annotation using nonnegative matrix factorization). BMC Bioinformatics, 11(S-6):S14, 2010. Google Scholar
  20. S. A. Vavasis. On the complexity of nonnegative matrix factorization. SIAM Journal on Optimization, 20(3):1364-1377, 2009. Google Scholar
  21. T. Yokota, R. Zdunek, A. Cichocki, and Y. Yamashita. Smooth nonnegative matrix and tensor factorizations for robust multi-way data analysis. Signal Processing, 113:234-249, 2015. Google Scholar
  22. S. Zhang, W. Wang, J. Ford, and F. Makedon. Learning from incomplete ratings using non-negative matrix factorization. In Proceedings of the 6th SIAM International Conference on Data Mining, pages 549-553. SIAM, 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact