The Library
On restricted nonnegative matrix factorization
Tools
Chistikov, D., Kiefer, S., Marusic, I., Shirmohammadi, M. and Worrell, J. (2016) On restricted nonnegative matrix factorization. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy, 12-15 Jul 2016. Published in: Leibniz International Proceedings in Informatics, LIPIcs, 55 103:1-103:14. ISBN 9783959770132. ISSN 1868-8969.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: 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.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Leibniz International Proceedings in Informatics, LIPIcs | ||||
Publisher: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik | ||||
ISBN: | 9783959770132 | ||||
ISSN: | 1868-8969 | ||||
Official Date: | 2016 | ||||
Dates: |
|
||||
Volume: | 55 | ||||
Page Range: | 103:1-103:14 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) | ||||
Type of Event: | Conference | ||||
Location of Event: | Rome, Italy | ||||
Date(s) of Event: | 12-15 Jul 2016 | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |