(3.237.97.64) 您好!臺灣時間:2021/03/09 09:35
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:黃聖堯
研究生(外文):Sheng-Yao Huang
論文名稱:高斯隨機投影下的快速近似奇異值分解
論文名稱(外文):Fast Approximation for SVD via Gaussian Random Projections
指導教授:陳素雲陳素雲引用關係
指導教授(外文):Su-Yun Huang
口試委員:洪弘陳宏
口試委員(外文):Hung HungHung Chen
口試日期:2019-07-17
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:應用數學科學研究所
學門:數學及統計學門
學類:其他數學及統計學類
論文種類:學術論文
論文出版年:2019
畢業學年度:107
語文別:英文
論文頁數:21
中文關鍵詞:矩陣角度高斯分配隨機化算法隨機投影奇異值分解
DOI:10.6342/NTU201902652
相關次數:
  • 被引用被引用:0
  • 點閱點閱:37
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
奇異值分解 (SVD) 是一個有名的矩陣分解的工具,但在矩陣的大小過大時將會計算得很久。Rokhlin et al. [1] 對快速 SVD 近似提供一個隨機化算法 (稱作 rSVD)。方法是首先先用高斯隨機投影將矩陣的行 (column) 或列 (row) 做一個縮減,然後再對這個叫低維度的子空間做 SVD。Chen et al. [2] 證明了 rSVD 的一致性 (consistency),本篇論文對 rSVD 的一致性給一個新的證明,證明方法為從矩陣角度高斯分配去做。Chen et al. [2] 還提出了一個根據高斯隨機投影的迭代法,此方法叫做 iSVD。除了一致性的證明外,還給了一個對圖片做低維度的估計當作例子。從例子的結果來看,可以發現到 iSVD 的計算時間比 SVD 少了許多,但出來的結果卻很相似。最後給了一個 iSVD 的python code,code 根據 Kolmogorov-Nagumo-type average 來完成。
Singular value decomposition (SVD) is a popular tool for dimension re-duction. When the size of matrix is large, the computing load is heavy. Rokhlin et al [1] proposed a randomized algorithm for fast SVD approxi-mation (abbreviated as rSVD). Often Gaussian random projection is used to reduce the number of columns or rows, and next SVD is carried out in this lower-dimensional subspace. Chen et al. [2] proved the consistency of rSVD. In this paper, we give the rSVD consistency a new proof. Our new proof is based on matrix angular Gaussian distribution and is more instructive. Chen et al. [2] further proposed an integration method based on multiple random Gaussian projections, called iSVD. In addition to the new proof for consis-tency, we also provide an iSVD example for image low-rank approximation. From this example, we can see that the runtime of iSVD is less than the run-time of SVD without sacrificing much of accuracy. Finally, we provide a python code for iSVD, it is based on Kolmogorov-Nagumo-type average.
誌謝 iii
Acknowledgements iv
摘要 v
Abstract vi
1 Introduction 1
2 Literature review 2
2.1 Stiefel manifold 2
2.2 Matrix-variate Gaussian distribution 3
2.3 Randomized SVD (rSVD) 3
2.4 Integration of multiple randomized SVDs (iSVD) 4
3 Main result 5
3.1 Consistency Theorem 5
3.2 New proof of Theorem 3.1.1 5
4 Numerical example 11
5 Conclusion 13
A Appendix 14
A.1 Matlab code 14
A.2 Python code 16
Bibliography 21
[1]Vladimir Rokhlin, Arthur Szlam, and Mark Tygert. A randomized algorithm for prin-cipal component analysis. SIAM Journal on Matrix Analysis and Applications, 2009.
[2]Ting-Li Chen, Dawei D. Chang, Su-Yun Huang, Hung Chen, Chien-Yao Lin, and Wei-Chung Wang. Intergrating multiple random sketches for singular value decom-position. arXiv preprint, 2016.
[3]Yasuko Chikuse. Statistics on Special Manifolds. Springer, 2003.
[4] Xiying rainbow bridge. https://www.penghunsa.gov.tw/FileDownload/Album/NotSet/20161012162551758864338.jpg.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文
 
系統版面圖檔 系統版面圖檔