Block-quantized kernel matrix for fast spectral embedding

Eigendecomposition of kernel matrix is an indispensable procedure in many learning and vision tasks. However, the cubic complexity O(N³) is impractical for large problem, where N is the data size. In this paper, we propose an efficient approach to solve the eigendecomposition of the kernel matrix W. The idea is to approximate W with W̄ that is composed of m ² constant blocks. The eigenvectors of W̄, which can be solved in O(m³) time, is then used to recover the eigenvectors of the original kernel matrix. The complexity of our method is only O(mN + m ³), which scales more favorably than state-of-the-art low rank approximation and sampling based approaches (O(m²N + m³)), and the approximation quality can be controlled conveniently. Our method demonstrates encouraging scaling behaviors in experiments of image segmentation (by spectral clustering) and kernel principal component analysis.