Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive Sampling
\nameShusen Wang \addrCollege of Computer Science and Technology Zhejiang University Hangzhou, Zhejiang 310027, China \AND\nameZhihua Zhang \addrDepartment of Computer Science and Engineering Shanghai Jiao Tong University 800 Dong Chuan Road, Shanghai, China 200240 Corresponding author.
Abstract
The CUR matrix decomposition and the Nyström approximation are two important low-rank matrix approximation techniques. The Nyström method approximates a symmetric positive semidefinite matrix in terms of a small number of its columns, while CUR approximates an arbitrary data matrix by a small number of its columns and rows. Thus, CUR decomposition can be regarded as an extension of the Nyström approximation.
中文速览
大规模矩阵的低秩近似是数据分析的核心问题，但现有的CUR分解和Nyström近似算法要么需要采样大量列/行、计算代价高昂，要么误差界较弱、无法达到相对误差保证。本文提出了一种更通用的"自适应列/行采样误差界"（adaptive sampling bound），以此为基础设计了新的CUR算法和修正Nyström算法，在理论上同时对列空间和行空间的投影误差给出相对误差保证，而无需对数据矩阵做任何特殊假设。新CUR算法在所需采样列/行数量和计算时间上均优于经典的子空间采样算法（subspace sampling），同时内存友好、无需将整个矩阵载入RAM；新Nyström算法的精度也显著优于标准Nyström和集成Nyström方法，后两者的误差下界甚至比一些CUR算法的误差上界还差。这项工作为大规模核矩阵近似和数据降维提供了更高效、更精确的理论与算法工具。
原文 arXiv:1303.4207;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1303.4207v7