{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T16:21:41Z","timestamp":1756570901288},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,8]]},"abstract":"<jats:p>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\u00a0dequantizing 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.<\/jats:p>","DOI":"10.24963\/ijcai.2019\/627","type":"proceedings-article","created":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:46:05Z","timestamp":1564285565000},"page":"4511-4517","source":"Crossref","is-referenced-by-count":5,"title":["A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix Factorization"],"prefix":"10.24963","author":[{"given":"Zhihuai","family":"Chen","sequence":"first","affiliation":[{"name":"CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, 100190, Beijing, China"},{"name":"University of Chinese Academy of Sciences, 100049, Beijing, China"}]},{"given":"Yinan","family":"Li","sequence":"additional","affiliation":[{"name":"Centrum Wiskunde & Informatica and QuSoft, Science Park 123, 1098XG Amsterdam, Netherlands"}]},{"given":"Xiaoming","family":"Sun","sequence":"additional","affiliation":[{"name":"CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, 100190, Beijing, China"},{"name":"University of Chinese Academy of Sciences, 100049, Beijing, China"}]},{"given":"Pei","family":"Yuan","sequence":"additional","affiliation":[{"name":"CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, 100190, Beijing, China"},{"name":"University of Chinese Academy of Sciences, 100049, Beijing, China"}]},{"given":"Jialin","family":"Zhang","sequence":"additional","affiliation":[{"name":"CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, 100190, Beijing, China"},{"name":"University of Chinese Academy of Sciences, 100049, Beijing, China"}]}],"member":"10584","event":{"number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2019","name":"Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}","start":{"date-parts":[[2019,8,10]]},"theme":"Artificial Intelligence","location":"Macao, China","end":{"date-parts":[[2019,8,16]]}},"container-title":["Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:50:33Z","timestamp":1564285833000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2019\/627"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2019,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2019\/627","relation":{},"subject":[],"published":{"date-parts":[[2019,8]]}}}