Quantum-Inspired Classical Algorithm for Principal Component Regression
  This paper presents a sublinear classical algorithm for principal component
regression. The algorithm uses quantum-inspired linear algebra, an idea
developed by Tang. Using this technique, her algorithm for recommendation
systems achieved runtime only polynomially slower than its quantum counterpart.
Her work was quickly adapted to solve many other problems in sublinear time
complexity. In this work, we developed an algorithm for principal component
regression that runs in time polylogarithmic to the number of data points, an
exponential speed up over the state-of-the-art algorithm, under the mild
assumption that the input is given in some data structure that supports a
norm-based sampling procedure. This exponential speed up allows for potential
applications in much larger data sets.
