Affiliations: [a] School of Computer Science, Tel Aviv University, Tel Aviv, Israel | [b] School of Computer Science, The Academic College of Tel Aviv-Yaffo, Tel Aviv, Israel
Correspondence:
[*]
Corresponding author: Alon Schclar, School of Computer Science, The Academic College of Tel Aviv-Yaffo, Tel Aviv 61083, Israel. E-mail:mailto:alonschc@mta.ac.il
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 ∈ Rm× n, a user defined integer
s≤ min(m, n) and A_M ∈ Rs× 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.
