A Quantum-inspired Algorithm for General Minimum Conical Hull Problems

Abstract

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.

References in corpus (13)

• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum principal component analysis
• Quantum algorithms for supervised and unsupervised machine learning
• Quantum-Inspired Support Vector Machine
• Quantum gradient descent for linear systems and least squares
• Quantum-inspired algorithms in practice
• Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization
• Quantum Perceptron Models
• Quantum Recommendation Systems
• Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
• Quantum algorithms and lower bounds for convex optimization
• Quantum Divide-and-Conquer Anchoring for Separable Non-negative Matrix Factorization

Cited by in corpus (6)

• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• A Grover-search Based Quantum Learning Scheme for Classification
• Quantum Differentially Private Sparse Regression Learning
• A brief introduction to quantum algorithms
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
• A quantum-inspired algorithm for approximating statistical leverage scores