计算奇异值分解 (SVD) 的有效算法是什么?

机器算法验证 主成分分析 算法 svd 数字
2022-01-28 12:08:30

维基百科关于主成分分析的文章指出

存在计算 SVD 的有效算法X无需形成矩阵XTX,因此计算 SVD 现在是从数据矩阵计算主成分分析的标准方法,除非只需要少数几个成分。

有人能告诉我这篇文章所说的有效算法是什么吗?没有给出参考(建议这种计算方式的文章的 URL 或引用会很好)。

1个回答

SVD 计算背后的主要工作是QR 算法话虽如此,有许多不同的算法来计算泛型的奇异值分解M-经过-N矩阵A. 此处(来自 Intel 的MKL的文档)关于该问题的一个很好的示意图如下:在此处输入图像描述

正如您所看到的,根据您的用例,有不同的方法(可以在此处找到例程命名约定)。这是因为,例如,在某些矩阵形式中,Householder 减少可能比Givens 旋转更昂贵(举出两种“明显”的获取 QR 的方式)。关于此事的标准参考资料是 Golub 和 Van Loan 的矩阵计算(我建议至少使用第 3 版)。我也找到了Å。Björck's Numerical Methods for Least Squares Problems非常好的资源;虽然 SVD 不是本书的主要重点,但它有助于将它的使用情境化。

如果我必须就此事给你一个一般性建议,那就是不要尝试编写自己的 SVD 算法,除非你已经成功上过几门数值线性代数的课程并且你知道自己在做什么。我知道这听起来违反直觉,但实际上,有很多东西可能会出错,而你最终会得到(充其量)次优的实现(如果没有错的话)。在这个问题上有一些非常好的免费套件(例如EigenArmadilloTrilinos等等。)