截断奇异值分解(Truncated Singular Value Decomposition)。
采用随机化 SVD 算法(Halko, Martinsson, Tropp, 2009,即 sklearn TruncatedSVD(solver="randomized") 所使用的算法),针对高维稀疏矩阵 进行截断的奇异值分解:只计算并保留前 k 个最大奇异值所对应的分量, 从而将一个 m×n 的稀疏矩阵降维为 m×k 的稠密(非稀疏)矩阵。
与完整的 SingularValueDecomposition(LINPACK 稠密算法, 需要将矩阵完全稠密化,O(m·n) 内存)不同,本算法在整个计算流程中 仅依赖稀疏矩阵-向量乘法(A·x 与 Aᵀ·y,均为 O(nnz) 复杂度), 不会将原始高维稀疏矩阵稠密化,时间复杂度为 O(nnz·ℓ·(2q+3) + (m+n)·ℓ² + ℓ³),空间复杂度为 O(nnz + (m+n)·ℓ), 其中 ℓ = k + 过采样维度,q 为幂迭代次数。
A ≈ U·Σ·Vᵀ,其中 U 为 m×k 的列正交矩阵(左奇异向量), Σ 为 k 个降序排列的奇异值,V 为 n×k 的列正交矩阵(右奇异向量)。 降维结果通过 TruncatedSVD.ReducedMatrix(= U·Σ = A·V)获得。