gpt4 book ai didi

performance - 随机SVD奇异值

转载 作者:行者123 更新时间:2023-12-04 12:24:57 26 4
gpt4 key购买 nike

随机SVD通过使用k + p个随机投影提取前k个奇异值/向量来分解矩阵。这对于大型矩阵非常有效。

我的问题与算法输出的奇异值有关。如果执行完整的SVD,为什么值不等于前k个奇异值?

下面,我在R中有一个简单的实现。任何有关改进性能的建议将不胜感激。

rsvd = function(A, k=10, p=5) {
n = nrow(A)
y = A %*% matrix(rnorm(n * (k+p)), nrow=n)
q = qr.Q(qr(y))
b = t(q) %*% A
svd = svd(b)
list(u=q %*% svd$u, d=svd$d, v=svd$v)
}

> set.seed(10)

> A <- matrix(rnorm(500*500),500,500)

> svd(A)$d[1:15]
[1] 44.94307 44.48235 43.78984 43.44626 43.27146 43.15066 42.79720 42.54440 42.27439 42.21873 41.79763 41.51349 41.48338 41.35024 41.18068

> rsvd.o(A,10,5)$d
[1] 34.83741 33.83411 33.09522 32.65761 32.34326 31.80868 31.38253 30.96395 30.79063 30.34387 30.04538 29.56061 29.24128 29.12612 27.61804

最佳答案

计算

我认为您的算法是对Martinsson et al.算法的修改。如果我正确理解的话,这特别是指低阶矩阵的近似值。我可能是错的。

可以通过A(500)的实际等级与k(10)和p(5)的值之间的巨大差异轻松解释这种差异。另外,Martinsson等人提到p的值实际上应该大于k的选定值。

因此,如果我们在考虑您的解决方案的情况下应用您的解决方案,请使用:

set.seed(10)
A <- matrix(rnorm(500*500),500,500) # rank 500
B <- matrix(rnorm(500*50),500,500) # rank 50

从时序上我们发现,与原始svd算法相比,使用更大的p值仍会导致极大的提速。
> system.time(t1 <- svd(A)$d[1:5])
user system elapsed
0.8 0.0 0.8

> system.time(t2 <- rsvd(A,10,5)$d[1:5])
user system elapsed
0.01 0.00 0.02

> system.time(t3 <- rsvd(A,10,30)$d[1:5])
user system elapsed
0.04 0.00 0.03

> system.time(t4 <- svd(B)$d[1:5] )
user system elapsed
0.55 0.00 0.55

> system.time(t5 <-rsvd(B,10,5)$d[1:5] )
user system elapsed
0.02 0.00 0.02

> system.time(t6 <-rsvd(B,10,30)$d[1:5] )
user system elapsed
0.05 0.00 0.05

> system.time(t7 <-rsvd(B,25,30)$d[1:5] )
user system elapsed
0.06 0.00 0.06

但是我们看到对于较低的秩矩阵使用较高的p确实可以提供更好的近似值。如果我们让k也更接近秩,则实际解和近似值之间的差将变为appx。 0,而速度增益仍然很大。
> round(mean(t2/t1),2)
[1] 0.77

> round(mean(t3/t1),2)
[1] 0.82

> round(mean(t5/t4),2)
[1] 0.92

> round(mean(t6/t4),2)
[1] 0.97

> round(mean(t7/t4),2)
[1] 1

因此,总的来说,我相信可以得出以下结论:
  • p应该选择为p> k(如果我正确的话,Martinsson称它为l)
  • k与rank(A)不应有太大差异
  • 对于低秩矩阵,结果通常更好。


  • 优化:

    就我而言,这是一种整齐的方法。实际上,我真的找不到更好的方法。我唯一能说的是建议不要使用 t(q) %*% A构造。为此,应该使用 crossprod(q,A),它应该快一点。但是在您的示例中,这种差异是不存在的。

    关于performance - 随机SVD奇异值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4224031/

    26 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com