  Quantum-inspired singular value decomposition (SVD) is a technique to perform
SVD in logarithmic time with respect to the dimension of a matrix, given access
to the matrix embedded in a segment-tree data structure. The speedup is
possible through the efficient sampling of matrix elements according to their
norms. Here, we apply it to extreme learning which is a machine learning
framework that performs linear regression using random feature vectors
generated through a random neural network. The extreme learning is suited for
the application of quantum-inspired SVD in that it first requires transforming
each data to a random feature during which we can construct the data structure
with a logarithmic overhead with respect to the number of data. We implement
the algorithm and observe that it works order-of-magnitude faster than the
exact SVD when we use high-dimensional feature vectors. However, we also
observe that, for random features generated by random neural networks, we can
replace the norm-based sampling in the quantum-inspired algorithm with uniform
sampling to obtain the same level of test accuracy due to the uniformity of the
matrix in this case. The norm-based sampling becomes effective for more
non-uniform matrices obtained by optimizing the feature mapping. It implies the
non-uniformity of matrix elements is a key property of the quantum-inspired
SVD. This work is a first step toward the practical application of the
quantum-inspired algorithm.
