有哪些快速算法可用於計算截斷 SVD？

可能在這裡偏離主題，但已經存在幾個（一、二）相關問題。

在文獻中四處尋找（或谷歌搜索截斷 SVD 算法）發現了很多以各種方式使用截斷 SVD 的論文，並**聲稱（令人沮喪，通常沒有引用）有快速的算法來計算它，但沒有人似乎在指出這些算法是什麼。

我唯一能找到的是一個單一的隨機算法，用在redSVD 庫中。

我想看到的是一組精確和不精確的算法，適合理解系統是如何工作的（但不一定要實際實現它們！）。

有沒有人對這種事情有很好的參考？

從廣義上講，有兩種計算特徵值或奇異值分解的方法。一種方法是將矩陣對角化，這基本上同時產生整個特徵值/奇異值分解（整個特徵值譜），請參閱此處的一些概述：什麼是計算奇異值分解（SVD）的有效算法？另一種方法是使用迭代算法，一次產生一個（或多個）特徵向量。在計算出所需數量的特徵向量後，可以停止迭代。

我認為沒有專門針對 SVD 的迭代算法。這是因為可以計算 SVD矩陣通過對正方形對稱進行特徵分解矩陣

因此，與其問什麼算法計算截斷的 SVD，不如問什麼迭代算法計算特徵分解： 最簡單的迭代算法稱為冪迭代，確實非常簡單：

1. 隨機初始化.
2. 更新.
3. 標準化.
4. 除非收斂，否則轉到第 2 步。

所有更複雜的算法最終都基於冪迭代的思想，但確實變得相當複雜。必要的數學由Krylov 子空間給出。算法是Arnoldi 迭代（用於方形非對稱矩陣）、Lanczos 迭代（用於方形對稱矩陣）及其變體，例如“隱式重啟 Lanczos 方法”等。

您可以在例如以下教科書中找到此描述：

1. Golub & Van Loan，矩陣計算
2. Trefethen & Bau，數值線性代數
3. Demmel，應用數值線性代數
4. Saad，大特徵值問題的數值方法

所有合理的編程語言和統計數據包（Matlab、R、Python numpy 等）都使用相同的 Fortran 庫來執行特徵/奇異值分解。這些是LAPACK和ARPACK。ARPACK 代表 ARnoldi PACKage，它完全是關於 Arnoldi/Lanczos 的迭代。例如，在 Matlab 中，SVD 有兩個函數：svd通過 LAPACK 執行完全分解，並svds通過 ARPACK 計算給定數量的奇異向量，它實際上只是eigs對“平方化”矩陣的調用的包裝器。

更新

事實證明，Lanczos 算法的變體專門用於執行矩形矩陣的 SVD無需顯式構造方陣第一的。這裡的中心術語是Lanczos bidiagonalization；據我了解，執行 Lanczos 迭代的所有步驟本質上是一個技巧直接上從來沒有建造過從而節省空間和時間。

這些方法也有一個 Fortran 庫，它被稱為PROPACK：

軟件包 PROPACK 包含一組用於計算大型和稀疏或結構化矩陣的奇異值分解的函數。SVD 例程基於具有部分重正交化 (BPRO) 的 Lanczos 雙對角化算法。

但是，PROPACK 似乎遠不如 ARPACK 標準，並且在標準編程語言中不原生支持。它由 Rasmus Larsen 撰寫，他在 1998 年有一篇長達 90 頁的大型論文Lanczos bidiagonalization with partial reorthogonalization似乎是一個很好的概述。感謝@MichaelGrant 通過這個計算科學 SE 線程。

在最近的論文中，最受歡迎的似乎是 Baglama & Reichel，2005，Augmented 隱式重啟了 Lanczos bidiagonalization methods，這可能是最先進的。感謝@Dougal 在評論中提供此鏈接。

更新 2

您自己引用的概述論文中確實詳細描述了一種完全不同的方法：Halko et al。2009，尋找具有隨機性的結構：構造近似矩陣分解的概率算法。我對它的了解不夠多，無法發表評論。

引用自：https://stats.stackexchange.com/questions/159325