Quantum-inspired algorithm for general minimum conical hull problems
Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Dacheng Tao · Physical Review Research · 2020
A wide range of fundamental machine learning tasks that are addressed by the maximum a posteriori estimation can be reduced to a general minimum conical hull problem.The best-known solution to tackle general minimum conical hull problems is the divide-and-conquer anchoring learning scheme (DCA), whose runtime complexity is polynomial in size.However, big data are pushing these polynomial algorithms to their performance limits.In this paper, we propose a sublinear classical algorithm to tackle general minimum conical hull problems when the input has stored in a sample-based low-overhead data structure.The algorithm's runtime complexity is polynomial in the rank and polylogarithmic in size.The proposed algorithm achieves the exponential speedup over DCA and, therefore, provides advantages for high-dimensional problems.