Matrix compression using the Nyström method

Abstract

The Nyström method is routinely used for out-of-sample extension of kernel matrices. We extend the applicability of this method and describe how it can be applied to find the singular value decomposition (SVD) of general matrices and the eigenvalue decomposition (EVD) of square matrices. We take as an input a matrix M ∈ R^{m× n}, a user defined integer s≤ min(m, n) and A_M ∈ R^{s× s}, a matrix sampled from the columns and rows of M. These are used to construct an approximate rank-s SVD of M in O(s^2(m+n)) operations. If M is square, the rank-s EVD can be similarly constructed in O(s^2 n) operations. The contribution of the proposed method is three-fold: first, it allows the compression of a general matrix M where the matrix A_M provides a compressed version of M. Second, it allows the approximation of the SVD and EVD when they cannot be directly calculated due to space and time limitations in case of large matrices. Third, a novel algorithm for selecting the initial sample is presented. The sample choice reduces the Nyström approximation error. We discuss the choice of A_M and propose an algorithm that selects a good initial sample for a pivoted version of $M$. The proposed algorithm performs well for general matrices and kernel matrices whose spectra exhibit fast decay.