請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/70483
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳素雲(Su-Yun Huang) | |
dc.contributor.author | Sheng-Yao Huang | en |
dc.contributor.author | 黃聖堯 | zh_TW |
dc.date.accessioned | 2021-06-17T04:29:11Z | - |
dc.date.available | 2019-08-19 | |
dc.date.copyright | 2019-08-19 | |
dc.date.issued | 2019 | |
dc.date.submitted | 2019-08-13 | |
dc.identifier.citation | [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. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/70483 | - |
dc.description.abstract | 奇異值分解 (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 來完成。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-17T04:29:11Z (GMT). No. of bitstreams: 1 U0001-0608201914494500.pdf: 2059320 bytes, checksum: ae25a17d06c0137487eb92a70cf3ff7b (MD5) Previous issue date: 2019 | en |
dc.description.tableofcontents | 誌謝 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 | |
dc.language.iso | en | |
dc.title | 高斯隨機投影下的快速近似奇異值分解 | zh_TW |
dc.title | Fast Approximation for SVD via Gaussian Random Projections | en |
dc.type | Thesis | |
dc.date.schoolyear | 109-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 洪弘(Hung Hung),陳宏(Hung Chen) | |
dc.subject.keyword | 矩陣角度高斯分配,隨機化算法,隨機投影,奇異值分解, | zh_TW |
dc.subject.keyword | matrix angular Gaussian distribution,randomized algorithm,random projection,Singular value decomposition, | en |
dc.relation.page | 21 | |
dc.identifier.doi | 10.6342/NTU201902652 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2019-08-13 | |
dc.contributor.author-college | 理學院 | zh_TW |
dc.contributor.author-dept | 應用數學科學研究所 | zh_TW |
顯示於系所單位: | 應用數學科學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-0608201914494500.pdf 目前未授權公開取用 | 2.01 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。