Kronecker Factorization for Speeding up Kernel Machines
Gang Wu, Zhihua Zhang, Edward Yi Chang · 2005
In kernel machines, such as kernel principal component analysis (KPCA), Gaussian Processes (GPs), and Support Vector Machines (SVMs), the computational complexity of finding a solution is O(n3), where n is the number of training instances. To reduce this expensive computational complexity, we propose using Kronecker factorization, which approximates a positive definite kernel matrix by the Kronecker product of two smaller positive definite matrices. This approximation can speed up the calculation of the kernel-matrix inverse or eigen-decomposition involved in kernel machines. When the two factorized matrices have about the same dimensions, the computational complexity is improved from O(n3) to O(n2). We propose two methods to carry out Kronecker factorization and apply them to speed up KPCA. In Experiments show that our methods can drastically reduce the computation time of kernel machines without any significant degradation in their effectiveness.