Making Large-Scale Nyström Approximation Possible
Making Large-Scale Nyström Approximation Possible
复制标题
DOI：
--
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
Mu Li;J. Kwok;Bao-Liang Lu
中科院分区：
文献类型：
--
作者：
Mu Li;J. Kwok;Bao-Liang Lu
Nystrom方法是求解大型核矩阵特征值分解的一种有效方法。然而，为了确保准确的近似，必须对足够大数量的列进行采样。在非常大的数据集上，所得数据子矩阵上的SVD步骤将很快主导计算并变得令人望而却步。在本文中，我们提出了一个准确的和可扩展的Nystrom计划，首先从输入矩阵的一个大的列子集的样本，但然后只执行一个近似的奇异值分解的内部子矩阵使用最近的随机低秩矩阵近似算法。理论分析表明，该算法是作为标准的Nystrom方法，直接执行一个大的奇异值分解的内部子矩阵一样准确。另一方面，它的时间复杂度仅与执行小SVD一样低。在大量的大规模数据集上进行了低秩近似和谱嵌入的实验。特别是，具有330万个样本的MNIST数据集的谱嵌入在具有4G内存的标准PC上需要不到一个小时。
The Nystrom method is an efficient technique for the eigenvalue decomposition of large kernel matrices. However, in order to ensure an accurate approximation, a sufficiently large number of columns have to be sampled. On very large data sets, the SVD step on the resultant data submatrix will soon dominate the computations and become prohibitive. In this paper, we propose an accurate and scalable Nystrom scheme that first samples a large column subset from the input matrix, but then only performs an approximate SVD on the inner submatrix by using the recent randomized low-rank matrix approximation algorithms. Theoretical analysis shows that the proposed algorithm is as accurate as the standard Nystrom 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. Experiments are performed on a number of large-scale data sets for low-rank approximation and spectral embedding. In particular, spectral embedding of a MNIST data set with 3.3 million examples takes less than an hour on a standard PC with 4G memory.