根据关于奇异值分解的维基百科文章,通过流行的 Householder QR 方法计算任意 m×n 矩阵 M(m>n)的 SVD 的渐近复杂度为 O(mn2)。是否有任何算法(可能是 Householder QR)可以为固定秩矩阵提供更好的渐近保证?
换句话说:设 Sn,k 是秩为 k 的 n×n 矩阵的集合。是否有算法可以提供比 O(n3) 更好的计算 Sn,k 元素的 SVD 作为 n→∞ 的渐近复杂度?
根据关于奇异值分解的维基百科文章,通过流行的 Householder QR 方法计算任意 m×n 矩阵 M(m>n)的 SVD 的渐近复杂度为 O(mn2)。是否有任何算法(可能是 Householder QR)可以为固定秩矩阵提供更好的渐近保证?
换句话说:设 Sn,k 是秩为 k 的 n×n 矩阵的集合。是否有算法可以提供比 O(n3) 更好的计算 Sn,k 元素的 SVD 作为 n→∞ 的渐近复杂度?
是的。您可以在矩阵上运行 rank-revealing QR, 这将在 step 停止(因此有效地终止于) 并产生, 在哪里仅在其第一个具有非零值行,和是正交的。您现在可以计算和 SVD, 并用它用一些矩阵产品来拼回成本的因素.