簡易檢索 / 詳目顯示

回結果列表
研究生： 林國陽
Lin, Guo-Yang
論文名稱： 奇異值分解擾動問題：一種正交 Procrustes 方法暨奇 異值分解的低秩修正方法之文獻整理與推導
An Orthogonal Procrustes Approach to Perturbation of Singular Value Decomposition (SVD) Problem and a Derivation of the Low-Rank Modification of SVD from Existing Literature
指導教授： 王辰樹
Wang, Chern-Shuh
學位類別： 碩士
Master
系所名稱： 理學院 - 數學系應用數學碩博士班
Department of Mathematics
論文出版年： 2025
畢業學年度： 113
語文別： 英文
論文頁數： 33
中文關鍵詞： 奇異值分解 、奇異值分解的低秩更新 、奇異值分解的擾動分析 、正交 Procrustes 問題 、Taylor-like 擾動展開式 、sin Θ 理論
外文關鍵詞： singular value decomposition, low-rank SVD modification, SVD perturbation analysis, orthogonal Procrustes problem, Taylor-like perturbation expansion, sin Θ theory
相關次數： 點閱：23  下載：3 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 本研究主要涵蓋兩個主題：其一為奇異值分解 (SVD) 的低秩更新問題，其二為 SVD 的擾動分析。針對前者，本文依據 Brand [2]、Gandhi et al. [5]、Golub [6] 及 Wilkinson [20] 等文獻，整理出一套完整的低秩更新演算法。
    除了 SVD 的低秩更新問題，本論文更加著墨於奇異值分解擾動問題。據我們所知，本研究提出一種具原創性的處理方法，其結合了用於處理正交 Procrustes 問題的技術與Taylor-like 擾動展開式的概念，從而推導出擾動矩陣 A˜ 在原矩陣 A 之零空間的正交補集的奇異值分解估計式。該估計式除了完整地保持奇異值分解的結構外，只需花費大約nmr + O ((n ∨ m)r^2) 的計算量 (若 A ∈ Rn×m 且 A 的秩是 r)。該估計式之誤差的收斂速度經數值實驗驗證為 O(k∆Ak)，屬於一階收斂。

    This study consists of two topics: the low-rank modification of singular value decomposition (SVD) and the perturbation analysis of SVD. For the former, we organize a complete algorithm for low-rank SVD modification problem based on the works of Brand [2], Gandhi et al. [5], Golub [6], and Wilkinson [20].
    The main contribution of this study lies in another topic, namely, the perturbation analysis of SVD. To the best of our knowledge, we propose an original approach that draws on the orthogonal Procrustes problem and incorporates Taylor-like perturbation expansions. This leads to an SVD approximation for A˜N(A)⊥ (perturbed matrix A˜ restricted to the orthogonal complement of the null space of the original matrix A) that preserves the SVD-structure and costs only approximately nmr + O ((n ∨ m)r^2) operations, where A ∈ Rn×m and rank(A) = r. Numerical experiments suggest that the residual term induced from the SVD approximation for A˜N(A)⊥ provided in this study exhibits first-order convergence, i.e., of order O(k∆Ak).

    Abstract i 摘要 ii 誌謝 iii List of Tables vi List of Figures vii Notations viii 1 Introduction 1 1.1 Problem Description 1 1.2 Literature Review 2 2 Low-Rank Modification of SVD 4 2.1 Rank-One Modification of a Diagonal Matrix 6 2.1.1 Orthogonal Diagonalization of the Matrix D + ρwwT 7 2.1.2 A Brief Discussion on the Computational Cost of Rank-One Updates 10 3 Perturbation of the SVD 11 3.1 Error Analysis 14 3.1.1 Numerical Justification 15 4 Conclusions 17 References 18 Appendix 20 A.1 det(I + uvT ) = 1 + vT u 20 A.2 Off-diagonal terms of Wˆ TWˆ 21 A.3 The solution of an orthogonal Procrustes problem 22 A.4 An explicit formula of σ′i in (3.15) 23

    [1] James Baglama, Vasilije Perović, and Timothy Toolan. “Note on a rank-one modification of the singular value decomposition”. In: Applied Mathematics and Computation 457 (2023), p. 128170. doi: 10.1016/j.amc.2023.128170.
    [2] Matthew Brand. “Fast low-rank modifications of the thin singular value decomposition”. In: Linear Algebra and its Applications 415 (2006), pp. 20–30. doi: 10.1016/j.laa.2005.07.021.
    [3] Jiu Ding and Aihui Zhou. “Eigenvalues of rank-one updated matrices with some applications”. In: Applied Mathematics Letters 20.12 (2007), pp. 1223–1226. doi: 10.1016/j.aml.2006.11.016.
    [4] Froilán M. Dopico. “A Note on Sin Θ Theorems for Singular Subspace Variations”. In: BIT Numerical Mathematics 40.2 (2000), pp. 395–403. doi: 10.1023/A:1022303426500.
    [5] Ratnik Gandhi and Amoli Rajgor. “Updating Singular Value Decomposition for Rank One Matrix Perturbation”. In: arXiv preprint arXiv:1707.08369 (2017). Available at https://arxiv.org/abs/1707.08369.
    [6] Gene H. Golub. “Some Modified Matrix Eigenvalue Problems”. In: SIAM Review 15.2 (1973), pp. 318–334.
    [7] Serge Gratton and Jean Tshimanga. “On a Second-Order Expansion of the Truncated Singular Subspace Decomposition”. In: Numerical Linear Algebra with Applications 23.3 (2016), pp. 519–534. doi: 10.1002/nla.2037.
    [8] Zhongxiao Jia and G. W. Stewart. “An Analysis of the Rayleigh–Ritz Method for Approximating Eigenspaces”. In: Mathematics of Computation 70.234 (2000), pp. 637–647. doi: 10.1090/S0025-5718-00-01208-4.
    [9] Fu Li and Richard J. Vaccaro. “Unified analysis for DOA estimation algorithms in array signal processing”. In: Signal Processing 25.2 (1991), pp. 147–169. doi: 10.1016/0165-1684(91)90060-V.
    [10] Jun Liu, Xiangqian Liu, and Xiaoli Ma. “First-Order Perturbation Analysis of Singular Vectors in Singular Value Decomposition”. In: IEEE Transactions on Signal Processing 56.7 (2008), pp. 3044–3049. doi: 10.1109/TSP.2007.916137.
    [11] Franklin T. Luk. “A Triangular Processor Array for Computing Singular Values”. In: Linear Algebra and its Applications 77 (1986), pp. 259–273. doi: 10.1016/0024-3795(86)90171-0.
    [12] L. Mirsky. “Symmetric Gauge Functions and Unitarily Invariant Norms”. In: The Quarterly Journal of Mathematics 11.1 (1960), pp. 50–59. doi: 10.1093/qmath/11.1.50.
    [13] Marc Moonen, Paul Van Dooren, and Joos Vandewalle. “A Singular Value Decomposition Updating Algorithm for Subspace Tracking”. In: SIAM Journal on Matrix Analysis and Applications 13.4 (1992), pp. 1015–1038. doi: 10.1137/0613061.
    [14] Peter H. Schönemann. “A Generalized Solution of the Orthogonal Procrustes Problem”. In: Psychometrika 31.1 (1966), pp. 1–10. doi: 10.1007/BF02289451.
    [15] G. W. Stewart. “Error and Perturbation Bounds for Subspaces Associated with Certain Eigenvalue Problems”. In: SIAM Review 15.4 (1973), pp. 727–764. doi: 10.1137/1015095.
    [16] G. W. Stewart. Perturbation Theory for the Singular Value Decomposition. Technical Report CS-TR-1990-1129. Department of Computer Science, University of Maryland, 1990. url: https://users.math.msu.edu/users/iwenmark/Teaching/MTH995/Papers/SVD_Stewart.pdf.
    [17] Richard J. Vaccaro. “A Second-Order Perturbation Expansion for the SVD”. In: SIAM Journal on Matrix Analysis and Applications 15.2 (1994), pp. 661–671. doi: 10.1137/S0895479891224245.
    [18] Trung Vu, Evgenia Chunikhina, and Raviv Raich. “Perturbation Expansions and Error Bounds for the Truncated Singular Value Decomposition”. In: Linear Algebra and its Applications 627 (2021), pp. 94–139. doi: 10.1016/j.laa.2021.05.020.
    [19] Hermann Weyl. “Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung)”. In: Mathematische Annalen 71.4 (1912), pp. 441–479. doi: 10.1007/BF01456804.
    [20] J. H. Wilkinson. The Algebraic Eigenvalue Problem. Oxford: Clarendon Press, 1965.
    [21] Zhengyuan Xu. “Perturbation Analysis for Subspace Decomposition with Applications in Subspace-Based Algorithms”. In: IEEE Transactions on Signal Processing 50.11 (2002), pp. 2820–2830. doi: 10.1109/TSP.2002.804084.

    下載圖示 校內：立即公開
    校外：立即公開
    QR CODE