论文标题
主要组件回归的量子启发的经典算法
Quantum-Inspired Classical Algorithm for Principal Component Regression
论文作者
论文摘要
本文提出了用于主要组件回归的均方根经典算法。该算法使用量子启发的线性代数，这是Tang开发的想法。使用此技术，她的算法用于推荐系统，其运行时仅比其量子速度较慢。她的作品很快被改编成解决均等时间复杂性中的许多其他问题。在这项工作中，我们开发了一种用于主成分回归的算法，该算法在时间的数据点数量中运行，该算法是在某些数据结构中给出的，该数据点比最新的算法高于最先进的算法，这是一个基于标准的采样程序的温和假设。这种指数速度提高允许在更大的数据集中进行潜在的应用程序。
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.
