Learning Low-Rank Kernel Matrices with Column-Based Methods

Abstract

We consider the problem of computing a low-rank approximation for large kernel matrix. In this article, a novel strategy called two-stage low-rank kernel matrix selection is proposed for computational efficiency enhancement. Firstly, two permutation sets are obtained by a proposed hybrid column-based selection method, which leads to significant reduction of kernel matrix in size. Secondly, entries of the resultant matrix are selected using information theoretic learning. Then this matrix is used for classification. Experimental results on real data sets have shown the superiority of the proposed method in terms of computational efficiency and classification accuracy, especially when training samples size is large.

Keywords:

• Kernel matrix
• Low-rank approximation
• QR decomposition

Mathematics Subject Classification:

• 68T10
• 62D05

Acknowledgments

The authors are grateful to the editors and referees for their helpful comments and suggestions. This work was supported by the National Natural Science Foundation of China (Grant No. 60533010) and the NSFC-Microsoft Research Asia Joint Research Fund (Grant No. 60933009).