高斯隨機投影下的快速近似奇異值分解

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 來完成。

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.