rSVD

一个用于使用随机算法计算矩阵近似奇异值分解（SVD）的Rust库。

背景

奇异值分解（SVD）是一种矩阵分解技术，在数据分析和科学计算中的许多应用中非常有用。然而，对于大型矩阵，计算完整的SVD可能会非常耗时。

随机算法提供了一种有效的方法来计算近似SVD，可以在显著少于原始矩阵的时间内捕获大部分动作。随机SVD背后的关键思想是

1. 使用随机测试矩阵来采样输入矩阵的范围
2. 正交化样本以获得捕获范围的子空间
3. 计算较小投影矩阵的SVD

这种技术允许在O(mn log k)时间内近似SVD，而不是完整的SVD所需的O(mn min(m,n))操作，其中m和n是输入矩阵的维度，k是目标秩。

特性

• 在O(mn log k)时间内计算矩阵的近似秩-k SVD
• 灵活选择目标秩k和过度采样参数p
• 通过ndarray-linalg使用BLAS/LAPACK以提高性能
• 纯Rust实现

使用方法

主函数是 rsvd()，它接受一个矩阵、目标秩k和过度采样参数p。它返回近似的SVD因子U、S和V^T。

use ndarray::{Array2, array};
use rsvd::rsvd;

let a = array!([1., 2., 3.],
               [8., 9., 4.],
               [7., 6., 5.]);

let (u, s, vt) = rsvd(&a, 2, 0, None);

应用

随机SVD对于许多涉及大型数据矩阵的应用非常有用

• 降维和特征提取
• 主成分分析（PCA）
• 推荐系统（协同过滤）
• 图像压缩
• 文本分析（LSA）

通过有效地近似SVD来捕获前k个奇异值/向量，随机SVD允许这些技术扩展到大规模数据集。

SVD还提供了一个强大的工具来分析和理解矩阵中包含的数据集的性质。奇异值指示每个组件的重要性，而奇异向量识别主成分。

参考文献

• 纳森·哈尔科等人。通过随机性寻找结构：构建近似矩阵分解的概率算法。（2011年）