A Quantum-inspired Algorithm for General Minimum Conical Hull Problems. (arXiv:1907.06814v1 [cs.LG])

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 is 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.

Article web page: