AB - © 2018 International Joint Conferences on Artificial Intelligence. All right reserved. It is NP-complete to find non-negative factors W and H with fixed rank r from a non-negative matrix X by minimizing ||X ? WH?||2F. Although the separability assumption (all data points are in the conical hull of the extreme rows) enables polynomial-time algorithms, the computational cost is not affordable for big data. This paper investigates how the power of quantum computation can be capitalized to solve the non-negative matrix factorization with the separability assumption (SNMF) by devising a quantum algorithm based on the divide-and-conquer anchoring (DCA) scheme [Zhou et al., 2013]. The design of quantum DCA (QDCA) is challenging. In the divide step, the random projections in DCA is completed by a quantum algorithm for linear operations, which achieves the exponential speedup. We then devise a heuristic post-selection procedure which extracts the information of anchors stored in the quantum states efficiently. Under a plausible assumption, QDCA performs efficiently, achieves the quantum speedup, and is beneficial for high dimensional problems.
AU - Du, Y
AU - Liu, T
AU - Li, Y
AU - Duan, R
AU - Tao, D
DA - 2018/01/01
EP - 2099
JO - IJCAI International Joint Conference on Artificial Intelligence
PY - 2018/01/01
SP - 2093
TI - Quantum divide-and-conquer anchoring for separable non-negative matrix factorization
VL - 2018-July
Y1 - 2018/01/01
Y2 - 2021/04/15
ER -