On Rationality of Nonnegative Matrix Factorization
On Rationality of Nonnegative Matrix Factorization
复制标题
论非负矩阵分解的合理性
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
J. Worrell
中科院分区：
文献类型：
--
作者：
D. Chistikov;S. Kiefer;Ines Marusic;M. Shirmohammadi;J. Worrell
非负矩阵分解（NMF）是将给定的非负n × m矩阵M分解为非负n × d矩阵W和非负d × m矩阵H的乘积的问题。NMF具有广泛的应用，包括生物信息学，化学计量学，通信复杂性，机器学习，多面体组合学等。Cohen和Rothblum在1993年提出了一个长期存在的问题，即是否每个有理矩阵M都有一个具有最小d的NMF，其因子W和H也是有理的。我们否定地回答这个问题，通过展示一个矩阵M，其中W和H需要无理项。作为这一结果的应用，我们表明，状态最小化的标记马尔可夫链可能需要引入不合理的转移概率。我们补充这些非理性的结果与NP完全版本的NMF的有理数足够。
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.
影响因子：
1.2
作者：
Chistikov D
通讯作者：
Chistikov D