An Improved Quantum Algorithm for Spectral Regression

Spectral Regression (SR) is a novel dimensionality reduction framework for efficient regularized subspace learning, which is fundamentally based on regression and spectral graph analysis. In this paper, we present a quantum algorithm for SR, where quantum Gram-Schmidt process are proposed and quantum singular value estimation (SVE) technique is applied for regression problem. The quantum algorithm involves two core phases: (1) With labels of the data set, we present a quantum Gram-Schmidt process subroutine based on the quantum block-encoding technique for generalized eigenvectors. (2) A quantum method for ridge regression is presented based on SVE, where the extended Hermitian form of the data matrix is not required. It is shown that our quantum algorithm can achieve an exponential speedup over the classical counterpart for the data matrix with well condition number and small sample size.