IEEE Trans Neural Netw Learn Syst. 2015 Jan;26(1):152-64. doi: 10.1109/TNNLS.2014.2359798. Epub 2014 Oct 8.
The Nyström method is an efficient technique for the eigenvalue decomposition of large kernel matrices. However, to ensure an accurate approximation, a sufficient number of columns have to be sampled. On very large data sets, the singular value decomposition (SVD) step on the resultant data submatrix can quickly dominate the computations and become prohibitive. In this paper, we propose an accurate and scalable Nyström scheme that first samples a large column subset from the input matrix, but then only performs an approximate SVD on the inner submatrix using the recent randomized low-rank matrix approximation algorithms. Theoretical analysis shows that the proposed algorithm is as accurate as the standard Nyström method that directly performs a large SVD on the inner submatrix. On the other hand, its time complexity is only as low as performing a small SVD. Encouraging results are obtained on a number of large-scale data sets for low-rank approximation. Moreover, as the most computational expensive steps can be easily distributed and there is minimal data transfer among the processors, significant speedup can be further obtained with the use of multiprocessor and multi-GPU systems.
Nyström 方法是一种用于大型核矩阵特征值分解的有效技术。然而，为了确保精确逼近，必须对足够数量的列进行采样。在非常大的数据集上，所得数据子矩阵上的奇异值分解（SVD）步骤可能会迅速占据主导地位，变得难以处理。在本文中，我们提出了一种准确且可扩展的 Nyström 方案，该方案首先从输入矩阵中采样一个大的列子集，但随后仅使用最近的随机低秩矩阵逼近算法对内部子矩阵执行近似 SVD。理论分析表明，所提出的算法与直接在内部子矩阵上执行大型 SVD 的标准 Nyström 方法一样准确。另一方面，其时间复杂度仅与执行小型 SVD 的复杂度相当。在许多大规模数据集上进行低秩逼近的实验结果表明，该算法是有效的。此外，由于最耗费计算资源的步骤可以轻松地分配，并且处理器之间的数据传输量最小，因此使用多处理器和多 GPU 系统可以进一步获得显著的加速效果。
