.png){kind=icon}
Return
Sketch Kernel Ridge Regression Using Circulant Matrix: Algorithm and Theory
.png){kind=icon}
PRE
AI
DOI：10.1109/TNNLS.2019.2944959.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Kernel ridge regression (KRR) is a powerful method for nonparametric regression. The time and space complexity of computing the KRR estimate directly are O(n(3)) and O(n(2)) , respectively, which are prohibitive for large-scale data sets, where n is the number of data. In this article, we propose a novel random sketch technique based on the circulant matrix that achieves savings in storage space and accelerates the solution of the KRR approximation. The circulant matrix has the following advantages: It can save time complexity by using the fast Fourier transform (FFT) to compute the product of matrix and vector, its space complexity is linear, and the circulant matrix, whose entries in the first column are independent of each other and obey the Gaussian distribution, is almost as effective as the i.i.d. Gaussian random matrix for approximating KRR. Combining the characteristics of the circulant matrix and our careful design, theoretical analysis and experimental results demonstrate that our proposed sketch method, making the estimate kernel methods scalable and practical for large-scale data problems, outperforms the state-of-the-art KRR estimates in time complexity while retaining similar accuracies. Meanwhile, our sketch method provides the theoretical bound that keeps the optimal convergence rate for approximating KRR.
Keywords:
Kernel
Training
Time complexity
Convergence
Acceleration
Approximation algorithms
Circulant matrix
kernel ridge regression (KRR)
large scale
random sketch
Journal
IF:
8.9
Papers:
7.6K
Citations:
7.2W
Organization
Cited Papers
ShareSaveShareSaveRANDOMIZED SKETCHES FOR KERNELS: FAST AND OPTIMAL NONPARAMETRIC REGRESSION.png)
ANNALS OF STATISTICS
OAAI
ANNALS OF STATISTICSIF3.7
OAAIShareSaveLocal rademacher complexities and oracle inequalities in risk minimizationANNALS OF STATISTICSOAAI
ANNALS OF STATISTICSIF3.7
OAAIShareSaveShareSaveShareSave
View more