Improving CUR Matrix Decomposition and the Nystrom Approximation via Adaptive Sampling

Abstraction: CUR and Nystrom low-rank approximation via adaptive column/row sampling

Key points:

• Authors Shusen Wang and Zhihua Zhang (JMLR 14(47):2729-2769, 2013)
• Nystrom method approximates a symmetric positive semidefinite matrix using a small number of its columns; CUR extends this to arbitrary matrices using both columns and rows
• Paper establishes more general error bounds for adaptive column/row sampling algorithms
• Proposed algorithms achieve expected relative-error bounds with low time complexity
• Algorithms can avoid loading the entire data matrix into RAM, enabling large-scale use
• Also provides lower error bound analysis for standard Nystrom and ensemble Nystrom methods

Connections: Cur Decomposition · Nystrom Approximation · Low Rank Matrix Approximation · Adaptive Sampling · Jmlr

Source: http://jmlr.org/papers/v14/wang13c.html