整合多重隨機奇異值分解與理論分析

Theoretical and Performance Analysis for Integrated Randomized Singular Value Decomposition

張大衛(Da-Wei Chang)

指導教授 ： 王偉仲

國立臺灣大學/理學院/應用數學科學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201702973

摘要

維度降低和特徵提取是大數據時代的重要技術，此二技術可以降低數據維數並降低進一步分析數據的計算成本。低秩奇異值分解（low-rank SVD）是這些技術的關鍵部分。為了更快地計算低秩奇異值分解，一些研究提出可以使用隨機抽取子空間的方法來獲得近似結果。在這項研究中，我們提出了一種新的概念，將隨機算法的結果進行整合以獲得更準確的近似值，稱為整合奇異值分解。我們通過理論和數值實驗來分析演算法的性質，以及不同的整合方法。整合方法的架構是有條件的優化問題，其具有唯一的局部極小值。整合子空間將透過線搜索、Kolmogorov-Nagumo 平均、和簡化類型的方法來進行計算，並針對這些方法的理論背景及計算複雜度進行分析，此外，整合奇異值分解與先前隨機奇異值分解的相似與相異處也會進行說明與分析。數值實驗結果顯示，在所提供的例子中，整合奇異值分解相對於同樣數量的隨機奇異值分解，使用線搜索方法時的疊代次數較少。另外，使用簡化類型的方法，來當作線搜索方法的初始值，可以減少收斂所需的疊代次數。

關鍵字

數值線性代數 ； 奇異值分解 ； 隨機演算法 ； 數值優化 ； 維度降低

並列摘要

Dimension reduction and feature extraction are the important techniques in the big-data era to reduce the dimension of data and the computational cost for further data analysis. Low-rank singular value decomposition (low-rank SVD) is the key part of these techniques. In order to compute low-rank SVD faster, some researchers propose to use randomized subspace sketching algorithm to get an approximation result (rSVD). In this research, we propose an idea for integrating the results from randomized algorithm to get a more accurate approximation, which is called integrated singular value decomposition (iSVD). We analyze iSVD and the integration methods by theoretical analysis and numerical experiment. The integration scheme is a constraint optimization problem with unique local maximizer up to orthogonal transformation. Line search type method, Kolmogorov-Nagumo type average method and reduction type method are introduced and analyzed for their theoretical background and computational complexity. The similarity and difference between iSVD and rSVD with same sketching number are also explained and analyzed. The numerical experiment shows that the line search method in iSVD converges faster than the one in rSVD for our test examples. Also, using the integrated subspace from reduction as the initial value of line search method can reduce the iteration number to converge.

並列關鍵字

Numerical Linear Algebra ； Singular Value Decomposition ； Randomized Algorithm ； Numerical Optimization ； Dimension Reduction

參考文獻

[4] T.-L. Chen, D. D. Chang, S.-Y. Huang, H. Chen, C. Lin, and W. Wang. Integrating multiple random sketches for singular value decomposition. arXiv preprint arXiv:1608.08285, 2016.

[1] P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, 2009.

[3] J. Barzilai and J. M. Borwein. Two-point step size gradient methods. IMA Journal of Numerical Analysis, 8(1):141–148, 1988.

[5] S.Fiori, T.Kaneko, and T.Tanaka. Mixed maps for learning a kolmogoroff-nagumo-type average element on the compact Stiefel manifold. IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP), pages 4518– 4522, 2014.

[7] N. Halko, P.-G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2):217–288, 2011.