The Library
On rationality of nonnegative matrix factorization
Tools
Tools
Tools
Chistikov, D., Kiefer, S., Marušić, I., Shirmohammadi, M. and Worrell, J. (2017) On rationality of nonnegative matrix factorization. In: Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 Jan 2017. Published in: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1290-1305. ISBN 9781611974782. ISSN 1071-9040. doi:10.1137/1.9781611974782.84
|
PDF
WRAP-rationality-nonnegative-matrix-factorization-Chistikov-2017.pdf - Accepted Version - Requires a PDF viewer. Download (818Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611974782.84
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. NMF has a wide variety of applications, including bioinformatics, chemometrics, communication complexity, machine learning, polyhedral combinatorics, among many others. A longstanding open question, posed by Cohen and Rothblum in 1993, is whether every rational matrix M has an NMF with minimal d whose factors W and H are also rational. We answer this question negatively, by exhibiting a matrix M for which W and H require irrational entries.
As an application of this result, we show that state minimization of labeled Markov chains can require the introduction of irrational transition probabilities.
We complement these irrationality results with an NP- complete version of NMF for which rational numbers suffice.
| Item Type: | Conference Item (Paper) | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||||||||
| Divisions: | Faculty of Science > Computer Science | |||||||||||||||
| Library of Congress Subject Headings (LCSH): | Algorithms, Matrices, Factorization (Mathematics) | |||||||||||||||
| Journal or Publication Title: | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms | |||||||||||||||
| Publisher: | SIAM | |||||||||||||||
| ISBN: | 9781611974782 | |||||||||||||||
| ISSN: | 1071-9040 | |||||||||||||||
| Official Date: | 2017 | |||||||||||||||
| Dates: |
|
|||||||||||||||
| Page Range: | pp. 1290-1305 | |||||||||||||||
| DOI: | 10.1137/1.9781611974782.84 | |||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||
| Publication Status: | Published | |||||||||||||||
| Access rights to Published version: | Open Access | |||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||
| Version or Related Resource: | http://wrap.warwick.ac.uk/97743/ | |||||||||||||||
| Conference Paper Type: | Paper | |||||||||||||||
| Title of Event: | Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | |||||||||||||||
| Type of Event: | Conference | |||||||||||||||
| Location of Event: | Barcelona, Spain | |||||||||||||||
| Date(s) of Event: | 16-19 Jan 2017 | |||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
