向矩陣添加新行後更新 SVD 分解
假設我有一個密集矩陣的大小，帶 SVD 分解
在
R我可以計算 SVD 如下svd(A)： 如果一個新的-th 行被添加到, 是否可以根據舊的 SVD 分解計算新的 SVD 分解（即通過使用,， 和)，無需從頭開始重新計算 SVD？
是的，可以在向現有矩陣添加一個新行後更新 SVD 分解。
通常，這種“加一”問題表述被稱為一級更新。@amoeba 提供的關於“特徵值分解的有效二級更新”的 MathOverflow 鏈接是一個很好的第一步，如果您想開始更深入地研究這個問題；第一篇論文為您的具體問題提供了明確的解決方案。只是為了澄清一階和二階的含義，這樣您就不會感到困惑，如果您的新是這樣的：
在哪裡和是向量，那麼您將其稱為一級更新（或擾動）。此更新的基本內容由Sherman-Morrison 公式決定。. 如果擾動超過一個等級，即。
伍德伯里公式開始發揮作用。如果您看到這些公式，您會注意到其中涉及很多逆。您不直接解決這些問題。由於您已經解決了他們的大量子系統（即您已經計算了一些分解），您可以利用這些來獲得更快和/或更穩定的估計。（這就是人們仍在研究這個領域的原因。）我經常參考 JE Gentle 的《計算統計》一書。我認為章。5數值線性代數將正確設置您。（不幸的是，Harville 的經典著作：“從統計學家的角度看矩陣代數”根本沒有涉及排名更新。）
從事物的統計/應用方面來看，排名第一的更新在推薦系統中很常見，因為每次新用戶註冊或新產品出現時，可能有數千個客戶條目並重新計算 SVD（或任何給定的分解）添加或刪除是非常浪費的（如果不是無法實現的話）。通常推薦系統矩陣是稀疏的，這使得算法更加高效。第一篇文章是 M. Brand 的“輕量級推薦系統的快速在線 SVD 修訂”手稿。進入密集矩陣我認為查看 Pattern Recognition and Imaging Processing 的論文可以讓你在使用實際算法方面走得很遠。例如論文：
- Ren 和 Dai 的人臉識別雙向主成分增量學習（2009），
- Li 等人關於增量和魯棒的子空間學習（2003 年）。
- Levey 和 Lindenbaum的順序 Karhunen-Loeve 基提取及其在圖像中的應用（2000 年）。
- Ross 等人的魯棒視覺跟踪增量學習 (2007)。
所有人似乎都在核心解決同樣的問題；新功能正在出現，我們需要相應地快速更新我們的表示。請注意，這些矩陣不是對稱的，甚至不是正方形的。M. Brand 的另一項工作也可以解決這個問題（參見論文“ Fast low-rank modifys of the thin奇異值分解（2006） ”——這也在帖子開頭給出的 MO 鏈接中提到。）有一個很多關於這個主題的優秀論文，但大多數都傾向於數學化（例如，Benaych-Georgesa 和 Nadakuditi 論文“大型矩形隨機矩陣的低秩擾動的奇異值和向量”（2012 年）") 而且我認為它們不會很快幫助您找到解決方案。我建議您繼續關注圖像處理文獻。
不幸的是，我沒有遇到任何一級更新例程的 R 實現。Computational Science SE 中關於“ Python、C 或 Fortran 中的可更新 SVD 實現？ ”的答案提供了許多您可能想要考慮的 MATLAB 和 C++ 實現。通常 R、Python 等實現是 C、C++ 或 FORTRAN 實現的包裝器。