"Matrix Compression using the Nystro\""om Method"

Authors Arik Nemtsov, Alon Schclar, Amir Averbuch

Abstract: The Nystr"{o}m method is routinely used for out-of-sample extension of kernel matrices. We describe how this method 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 i n m a t h b b R^{m i m e s n}

, a user defined integer

s l e q m i n (m, n)

and

A_{M} i n m a t h b b R^{s i m e 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 l e f t (s^{2} l e f t (m + n i g h t) i g h t)

operations. If

M

is square, the rank-

s

EVD can be similarly constructed in

O l e f t (s^{2} n i g h t)

operations. Thus, the matrix

A_{M}

is a compressed version of

M

. 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.

This page was built for publication: "Matrix Compression using the Nystro\""om Method"

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6511515)