Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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:
DateEvent
2017Published
29 January 2017Available
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:
Project/Grant IDRIOXX Funder NameFunder ID
ImPACTEuropean Research Councilhttp://viaf.org/viaf/130022607
AVS-ISS (648701)European Research Councilhttp://viaf.org/viaf/130022607
Fellowship[RS] Royal Societyhttp://dx.doi.org/10.13039/501100000288
UNSPECIFIED[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
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:
  • Other Repository
  • Open Access File

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us