arXiv (Cornell University) · 2019 · 18 citations · 24 references
ComputingComputer ScienceAlgorithmsMachine LearningQuantum ComputingKernel MethodsQuantum AlgorithmsQuantum ComputationQuantum Machine LearningSupport Vector MachinesBig Data ClassificationQuantum Algorithm Complexity AnalysisQuantum Learning TheoryQuantum Machine Learning AlgorithmsQuantum SpeedupQuantum Support Vector MachinesSampling
Support vector machine (SVM) is a particularly powerful and flexible supervised learning model that analyzes data for both classification and regression, whose usual algorithm complexity scales polynomially with the dimension of data space and the number of data points. To tackle the big data challenge, a quantum SVM algorithm was proposed, which is claimed to achieve exponential speedup for least squares SVM (LS-SVM). Here, inspired by the quantum SVM algorithm, we present a quantum-inspired classical algorithm for LS-SVM. In our approach, a improved fast sampling technique, namely indirect sampling, is proposed for sampling the kernel matrix and classifying. We first consider the LS-SVM with a linear kernel, and then discuss the generalization of our method to non-linear kernels. Theoretical analysis shows our algorithm can make classification with arbitrary success probability in logarithmic runtime of both the dimension of data space and the number of data points for low rank, low condition number and high dimensional data matrix, matching the runtime of the quantum SVM.
24
Chih-Chung Chang, Chih‐Jen Lin · ACM Transactions on Intelligent Systems and Technology · 2011 · 41.3K citations
Least Squares Support Vector Machine Classifiers
Johan A. K. Suykens, Joos Vandewalle · Neural Processing Letters · 1999 · 9.4K citations · Full text
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996 · 8.6K citations · Full text
Algorithms for quantum computation: discrete logarithms and factoring
Peter W. Shor · 2002 · 8.5K citations
Computing, Computer Science, Physics +12
Julia: A Fresh Approach to Numerical Computing
Jeff Bezanson, Alan Edelman, Stefan Karpinski et al. · SIAM Review · 2017 · 6.3K citations