基于不等概抽样与随机SVD分解的Nyström方法

Nyström Method Based on Unequal Probability Sampling and Random SVD Decomposition

对于大规模数据集,Nyström方法是一种较为有效的矩阵低秩逼近技术,旨在从原始数据矩阵中抽取部分列重构原始数据矩阵的低秩逼近矩阵。考虑到不同抽样方法对重构矩阵的精度有较大的影响,文章提出将不等概抽样Nyström方法与随机奇异值分解方法相结合,进而在矩阵重构过程中提高矩阵低秩逼近精度,并有效降低计算复杂度。研究结果表明,提出的Nyström方法在矩阵重构中具有较高的精确度,且可以极大地降低计算复杂度。

For large-scale datasets,Nyström method is a relatively effective low-rank matrix approximation technique,which aims to extract some columns from the original data matrix to reconstruct the low-rank approximation matrix of the original data matrix.Considering that different sampling methods have great influence on the accuracy of the reconstructed matrix,this paper proposes the idea of combining the unequal probability sampling Nyström method with random singular value decomposition method to improve the low-rank approximation accuracy of the matrix and effectively reduce the computational complexity.The results show that the Nyström method proposed in this paper has high accuracy in matrix reconstruction and can greatly reduce the computational complexity.