在我正在进行的一个软件项目中，对于密集的低秩矩阵，某些计算要容易得多。一些问题实例涉及密集的低秩矩阵，但它们是完整给我的，而不是作为因子，所以如果我想利用低秩结构，我将不得不检查秩和矩阵的因子.
所讨论的矩阵通常是完全或几乎完全密集的，n 的范围从一百到几千。如果矩阵具有低秩（例如小于 5 到 10），那么计算 SVD 并使用它形成低秩分解是值得的。然而，如果矩阵不是低秩的，那么努力就会被浪费掉。
因此，在投入精力进行完整的 SVD 分解之前，我想找到一种快速且合理可靠的方法来确定排名是否低。如果在任何时候很明显等级高于截止值，则该过程可以立即停止。如果程序错误地将矩阵声明为低秩而不是，这不是一个大问题，因为我仍然会做一个完整的 SVD 来确认低秩并找到一个低秩分解。
我考虑过的选项包括显示 LU 或 QR 分解的等级，然后是完整的 SVD 作为检查。还有其他我应该考虑的方法吗？
当然，问题在于计算真正的秩（例如，通过 QR 分解）并不比计算矩阵的低秩表示便宜。
您可能做的最好的事情是使用随机算法来找到低秩近似值。至少在理论上，这些可以比处理整个矩阵要快得多，因为从本质上讲，它们只计算矩阵在随机子空间上的投影的分解。
的矩阵是否值得这样做可能是一个好问题，但如果你的问题真的变得很大，我怀疑它会得到回报。
我最近从这篇论文中学到了一个巧妙的技巧。的矩阵时，你开始进行秩揭示 QR，并在前个Householder 反射 之后停止， 使用大小为三角形，并且通常不是三角形的（因为我们在主循环次迭代后停止了）。此时，您检查是否 : 如果它成立，则与秩为的矩阵的距离最大为
对于密集的矩阵，此过程花费
您可能感兴趣的另一种方法是随机抽样。如果您可以快速计算矩阵向量乘积和 ，这将特别有趣。核心思想是形成一个小的采样矩阵，其中是一个高斯随机矩阵。如果采样矩阵足够大，将捕获的范围。如果奇异值呈指数下降，情况尤其如此。
有关更多详细信息，您可以查看：
Halko N.、Martinsson P.-G.、Tropp JA “寻找具有随机性的结构：构造近似矩阵分解的概率算法”
另一种值得尝试的方法是使用自适应交叉逼近 (ACA)。这是一种非常流行的算法，在网上有很多实现。供参考，您可以查看原始论文：
ACA 及其变体（例如，ACA+，混合交叉近似 HCA）可用于不同的场景。您已经计算了整个密集矩阵是有利的之一，因为您将能够在需要时准确计算残差。
如果启发式残差（见算法）足够，我相信你的复杂性将是，其中是方阵的大小，是秩。请注意，秩是规定截断容差的函数。而准确和有保证的误差范围将需要。