Quantum-Inspired Classical Algorithm for Slow Feature Analysis
arXiv:2012.00824
Abstract
Recently, there has been a surge of interest for quantum computation for its ability to exponentially speed up algorithms, including machine learning algorithms. However, Tang suggested that the exponential speed up can also be done on a classical computer. In this paper, we proposed an algorithm for slow feature analysis, a machine learning algorithm that extracts the slow-varying features, with a run time O(polylog(n)poly(d)). To achieve this, we assumed necessary preprocessing of the input data as well as the existence of a data structure supporting a particular sampling scheme. The analysis of algorithm borrowed results from matrix perturbation theory, which was crucial for the algorithm's correctness. This work demonstrates the possible application and extent for which quantum-inspired computation can be used.
References in corpus (11)
- Quantum Machine Learning
- Quantum algorithm for solving linear systems of equations
- Quantum random access memory
- Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
- Quantum-inspired algorithms in practice
- Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
- Quantum Recommendation Systems
- Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
- Quantum classification of the MNIST dataset with Slow Feature Analysis
- An improved quantum-inspired algorithm for linear regression
- Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra