在过去的几周里，我一直在尝试用C实现SVD，目前我一直在使用这里找到的算法6，据我所知，该算法将在时间O（n^5）内运行，因为有两个循环（其中一个循环不会从0到n，我知道，但n^5是一个粗略的边界），在内环内必须进行矩阵乘法运算，这是一个n^3过程。
然而，根据这个网站，对于一个n乘n的矩阵，SVD可以用O（2n^3）来计算。有人知道我在哪里可以找到这种时间复杂性的算法吗？
如果将来有人在寻找这个问题的答案，如果矩阵是平方矩阵，则在O（n^3）中计算SVD的算法是Jacobi旋转的方法。
有关具体算法的更多信息，您可以在本网站上查看算法7。
由于拼写错误，网站上的注释有点令人困惑，但在确定d1、d2、c和č的值的步骤中（对不起，这是我在顶部戴帽子时能得到的最接近c的值），它们的意思是c=cos（θ）、s=sin（theta）、č=cos（phi）和š=sin。
你可以通过消除和替换来计算theta和phi的这些值，也可以查看StackExchange的这篇文章，看看如何计算它们。
在那之后，它只是遵循那个算法。
计算m×n矩阵的SVD具有复杂性O（mn min（n，m））。由于这在数据大小上是超线性的，因此对于大型数据集来说，它在计算上变得昂贵。然而，如果我们有一个低秩矩阵，我们将只需要k个基向量，其中k<lt；m、 n.计算秩k近似的一种方法是计算全矩阵的SVD，并且仅保留k个最大奇异值和向量。
https://arxiv.org/pdf/1710.02812.pdf