一种用于可分离的非负矩阵分解的量子启发经典算法

作者：Zhihuai Chen,Yinan Li,Xiaoming Sun,Pei Yuan,Jialin Zhang

摘要：非负矩阵分解（NMF）要求将（入口）非负矩阵分解为两个较小尺寸的非负矩阵的乘积，这一点已被证明是难以处理的。 为了克服这个问题，引入了可分性假设，假设所有数据点都在锥形船体中。 这种假设使NMF易于处理并广泛用于文本分析和图像处理，但对于大规模数据集仍然不切实际。 在本文的启发下，基于去量化技术的最新发展，我们提出了一种新的可分离NMF问题的经典算法。 我们的新算法在秩中的多项式时间和输入矩阵的大小中以对数运行，这在低秩设置中实现指数加速。

原文标题：A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix Factorization

原文摘要：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, the separability assumption is introduced which assumes all data points are in a conical hull. This assumption makes NMF tractable and is 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.

地址：https://arxiv.org/abs/1907.05568