固定秩 SVD 的渐近复杂度

计算科学 算法 复杂 svd
2021-12-22 20:29:20

根据关于奇异值分解的维基百科文章,通过流行的 Householder QR 方法计算任意 m×n 矩阵 M(m>n)的 SVD 的渐近复杂度为 O(mn2)。是否有任何算法(可能是 Householder QR)可以为固定秩矩阵提供更好的渐近保证?

换句话说:设 Sn,k 是秩为 k 的 n×n 矩阵的集合。是否有算法可以提供比 O(n3) 更好的计算 Sn,k 元素的 SVD 作为 n→∞ 的渐近复杂度?

1个回答

是的。您可以在矩阵上运行 rank-revealing QRA, 这将在 step 停止k(因此有效地终止于O(mnk)) 并产生A=QRP, 在哪里R仅在其第一个具有非零值k行,和Q,P是正交的。您现在可以计算和 SVDR, 并用它用一些矩阵产品来拼回成本的因素O(max(m,n)k2).