Towards More Efficient Symmetric Matrix Sketching and the CUR Matrix Decomposition
Shusen Wang, Zhihua Zhang, Tong Zhang · arXiv (Cornell University) · 2015
Matrix sketching schemes and the Nystr\om method have both been extensively used to speed up large-scale eigenvalue computation and kernel learning methods. Matrix sketching methods produce accurate matrix approximations, but they are only computationally efficient on skinny matrices where one of the matrix dimensions is relatively small. In particular, they are not efficient on large square matrices. The Nystr\om method, on the other hand, is highly efficient on symmetric (and thus square) matrices, but can only achieve low matrix approximation accuracy. In this paper we propose a novel combination of the sketching method and the Nystr\om method to improve their efficiency/effectiveness, leading to a novel approximation which we call the Sketch-Nystr\om method. The Sketch-Nystr\om method is computationally nearly as efficient as the Nystr\om method on symmetric matrices with approximation accuracy comparable to that of the sketching method. We show theoretically that the Sketch-Nystr\om method can potentially solve eigenvalue problems and kernel learning problems in linear time with respect to the matrix size to achieve $1+\epsilon$ relative-error, whereas the sketch methods and the Nystr\om method cost at least quadratic time to attain comparable error bound. Our technique can be straightforwardly applied to make the CUR matrix decomposition more efficiently computed without much affecting the accuracy. Empirical experiments demonstrate the effectiveness of the proposed methods.