(英) |
In 2016, the quantum recommendation system was proposed by Kerenidis and Prakash, and it was shown that the singular value decomposition of a matrix of dimension n is possible on a quantum computer with O(poly(logn)) time. Furthermore, the quantum inspired algorithm was proposed by Tang in 2018, and it was shown that with an appropriate sampling, singular value decomposition can be computed in O(poly(log n)) time on classical computers as well, which is called de-quantization. In this algorithm, the matrix, which is stored with a binary search tree structure, is sampled randomly according to the row and column L2 norms so that the matrix is compressed. Then the singular value decomposition is performed for the compressed matrix is singularly decomposed, and the singular vectors obtained are used to recover the singular vectors of the original matrix. This algorithm is based on a low-rank approximation and gives a good approximation when the rank of the matrix is small. In this pa- per, we propose an application of the quantum inspired singular value decomposition to machine learning, specifically extreme learning machine, and numerically verify the effectiveness of the low-rank approximation on standard data sets used in machine learning. |