A Quantum-Inspired Classical Algorithm for Separable Non-Negative Matrix Factorization

Zhihuai Chen, Yinan Li, Xiaoming Sun, Pei Yuan, Jialin Zhang

IJCAI 2019 pp. 4511-4517

doi:10.24963/IJCAI.2019/627 /ijcai/2019/chen2019ijcai-quantum/

Abstract

Non-negative Matrix Factorization (NMF) asks to decompose a (entry-wise) non-negative matrix into the product of two smaller-sized nonnegative matrices, which has been shown intractable in general. In order to overcome this issue, separability assumption is introduced which assumes all data points are in a conical hull. This assumption makes NMF tractable and widely used in text analysis and image processing, but still impractical for huge-scale datasets. In this paper, inspired by recent development on dequantizing techniques, we propose a new classical algorithm for separable NMF problem. Our new algorithm runs in polynomial time in the rank and logarithmic in the size of input matrices, which achieves an exponential speedup in the low-rank setting.

PDF IJCAI Semantic Scholar

Cite

Text

Chen et al. "A Quantum-Inspired Classical Algorithm for Separable Non-Negative Matrix Factorization." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/627

Markdown

[Chen et al. "A Quantum-Inspired Classical Algorithm for Separable Non-Negative Matrix Factorization." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/chen2019ijcai-quantum/) doi:10.24963/IJCAI.2019/627

BibTeX

@inproceedings{chen2019ijcai-quantum,
  title     = {{A Quantum-Inspired Classical Algorithm for Separable Non-Negative Matrix Factorization}},
  author    = {Chen, Zhihuai and Li, Yinan and Sun, Xiaoming and Yuan, Pei and Zhang, Jialin},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {4511-4517},
  doi       = {10.24963/IJCAI.2019/627},
  url       = {https://mlanthology.org/ijcai/2019/chen2019ijcai-quantum/}
}