计算科学 - 计算截断的 SVD，一次一个奇异值/向量 - 吾爱随笔录

计算截断的 SVD，一次一个奇异值/向量

计算科学线性代数算法 svd

2021-11-28 04:17:17

是否有一种截断的 SVD 算法可以一次计算一个奇异值？

我的问题：我想计算个奇异值（和奇异向量），但我不知道的合适值是多少。很大，因此出于效率原因，我宁愿不评估完整的 SVD，而只是在之后截断最小的 SV。 $k$ $M$ $k$ $M$

理想情况下，有一种方法可以从最大 ( ) 到最小 (。这样，低于某个阈值个奇异值后简单地停止计算。 $\sigma_1, \sigma_2,\ldots$ $\sigma_1$ $\sigma_n$ $k$ $\sigma_k/\sigma_1$

是否存在这样的算法（最好使用 Python 实现）？在我的谷歌搜索中，我只发现了以 k 作为参数的截断 SVD 函数，从而迫使你先验地猜测它。

2个回答

如果您想要近似的 rank-k 分解，有几个选项可用。

强秩显示 QR 分解
插值分解 (ID) 和其他随机技术。

一般来说，它们提供形式为

‖ A - M N^{T} ‖ \leq factor \times σ_{k + 1} (A) := ϵ

$\begin{equation}\| A - MN^T\| \leq \text{factor}\times \sigma_{k+1}(A) := \epsilon \end{equation}$

可以使用标准技术将上述形式的近似分解转换为标准分解，如 QR 或 SVD。Halko、Martinsson 和 Tropp 的论文“寻找具有随机性的结构：用于构造近似矩阵分解的概率算法”的论文中提供了很好的评论

就软件而言，在 scipy (scipy.linalg.interpolative) http://docs.scipy.org/doc/scipy-dev/reference/linalg.interpolative.html中提供了 ID 算法的接口，允许用户指定。 $\epsilon$

（已编辑，因为我起初误读了这个问题；您已经知道有一些例程可用于计算前个奇异值。） $k$

如果排除计算整个 SVD 的方法，部分 SVD 算法将简化为使用迭代方法来解决相关的 Hermitian 特征值问题。因此，您可以采取的一种策略是自己手动编写此类代码，并使用诸如移位和反转策略之类的方法，继续求解最大的剩余未求解奇异值，直到您想停止为止。在SLEPc等复杂的包中可能有一些优雅的方式来做这种事情。

另一种策略如下：

计算最大奇异值。 $s_{1}$
将稀疏 SVD 例程的绝对容差设置为，其中是您的阈值，而是一些安全系数，用于确定您想要多少可能无关的奇异值计算。 $\tau \cdot s_{1} \cdot f$ $\tau$ $0 < f \leq 1$
调用稀疏 SVD 例程。

如果稀疏 SVD 例程计算一个薄 SVD（我不明白为什么它不会），那么这个策略会给你所有你想要的奇异值（可能还有一些额外的），因为低于绝对容差的值会被视为零。在这种情况下，您可以使用scipy.sparse.linalg.svds，注意是一个可选参数，并且您不必先验地指定它。 $k$

其它你可能感兴趣的问题