机器算法验证 - 随机 SVD 和奇异值 - 吾爱随笔录

随机 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

    B <- matrix(rnorm(500*50),500,500)  # rank 50

> rsvd(B,10,5)$d
 [1] 86.48035 83.02114 81.03988 80.04358 77.24979 76.10945 74.47357 74.08382
 [9] 72.85898 72.06897 69.59526 67.70750 66.53867 62.96446 61.50838

> svd(B)$d[1:15]
 [1] 92.44779 91.47689 88.71948 88.08170 87.24533 85.13312 84.14741 83.71757
 [9] 82.80832 81.43005 80.73903 79.92959 78.87421 78.33509 77.38431

正如 Joris 指出的那样，我也在 stackoverflow 上发布了这个。你可以在这里找到相关的对话

https://stackoverflow.com/questions/4224031/randomized-svd-singular-values

另请参阅 Martinsson 等人的相关论文：矩阵分解的随机算法