炼数成金 门户 科学探索 算法 查看内容

SVD加速:rSVD

2020-6-29 14:35| 发布者: 炼数成金_小数| 查看: 8676| 评论: 0|来自: 纯真学者出神入化

摘要: 奇异值分解(SVD)是基本的线性代数操作,在机器学习、统计、信号处理和其他领域中无处不在,因而当之无愧的位列20世纪十大算法。实数m×n矩阵A的SVD是指形式上为A = UΣVᵀ的分解,其中U是左奇异向量,大小为m ...
随机SVD
SVD被誉为二十世纪十大算法之一,本文分享一个SVD的经典加速方法,随机SVD (randomized SVD, rSVD)。

原文来自于:
https://research.fb.com/blog/2014/09/fast-randomized-svd/。

Paragraph   1
奇异值分解(SVD)是基本的线性代数操作,在机器学习、统计、信号处理和其他领域中无处不在,因而当之无愧的位列20世纪十大算法。实数m×n矩阵A的SVD是指形式上为A = UΣVᵀ的分解,其中U是左奇异向量,大小为m×m的正交矩阵,Σ是奇异值的m×n对角矩阵, Vᵀ是右奇异向量的n×n正交矩阵。

SVD提供了A的低秩近似。即,找到一个r < m和n,以及矩阵Aᵣ,使得||Aᵣ– A ||的误差被最小化。给定A = UΣVᵀ,可以通过以下过程来近似A:

1. 按递减顺序对Σ的非零元素进行排序;
2. 取Σ的前r个元素(例如Σᵣ,一个r×r对角矩阵),U的对应列(Uᵣ,一个m×r正交矩阵)和V的对应列(Vᵣ,一个n×r正交矩阵) ;
3. 取Aᵣ=UᵣΣᵣVᵣᵀ。

在视觉上,低秩矩阵分解对应于下图:

我们可以证明Aᵣ满足各种最优性质(例如,在谱范数意义下,近似误差||Aᵣ– A ||是Σ的第(r + 1)对角元素)。

SVD技术在机器学习,数据挖掘,生物信息学乃至政治科学中都有大量应用:从通过将共现矩阵分解来预测主题标签,到通过分解立法者-法条矩阵来理解政治投票模式,再到机器学习中的维度约简。

尽管SVD十分有用,计算SVD对于常见的大规模问题可能非常耗时。这里我们讨论将随机方法(https://arxiv.org/abs/0909.4061)运用进来的一种SVD加速方法,可使得计算SVD明显提速。

Paragraph   2
rSVD算法分两个主要步骤进行。第一步是使用随机生成的方法来计算range(A)。也就是说,我们试图找到具有r个正交列且使得A≈QQᵀA的Q。理论证明,这样的Q确实可以通过随机生成的方法得到(https://arxiv.org/abs/0909.4061)。假设我们找到了这样的Q,那么我们可以更简单的计算A的SVD。

首先,构造B =QᵀA。由于B相对较小(回想Q仅具有少量列),我们可以通过标准方法有效地计算B的SVD,因此B = SΣVᵀ对于S,V正交和Σ对角线。然后,当A≈QQᵀA = Q(SΣVᵀ)时,我们看到,取U = QS,我们计算出了一个低秩近似A≈UΣVᵀ。

该算法的诀窍来自于有效地通过随机方法计算近似矩阵Q。直观地,为了估计矩阵range(A),我们可以取一组随机向量Ω1,Ω2,…,并检查由A作用于这些随机向量中的每一个而形成的子空间。如果我们形成一个n×l高斯随机矩阵Ω,计算Y = AΩ,并进行Y的QR分解: QR = Y,则Q是一个m×l矩阵,其列是range(Y)的正交基。

上述方法虽然是可行的,但是在理论上和近似上精度都有提高空间。

一种提高近似度的方法是对(AAᵀ)进行几次功率迭代,以降低Y的频谱。这里的关键是,如果A的奇异值为Σ,则(AAᵀ)^pA的奇异值为Σ^ {2p + 1},因此频谱(以及我们的近似误差)随着迭代次数呈指数衰减。实际上,一次或两次迭代就足够了(而对于有噪声的数据,p = 0通常是不够的)。为了在所有这些操作中保持数值精度,我们在功率迭代过程中进行了QR分解。

Paragraph   3
幸运的是,rSVD已经被sklearn兼容,我们可以直接使用

和ARPACK相比,性能如下


声明:文章收集于网络,版权归原作者所有,为传播信息而发,如有侵权,请联系小编删除,谢谢!

欢迎加入本站公开兴趣群
高性能计算群
兴趣范围包括:并行计算,GPU计算,CUDA,MPI,OpenMP等各种流行计算框架,超级计算机,超级计算在气象,军事,航空,汽车设计,科学探索,生物,医药等各个领域里的应用
QQ群:326600878

鲜花

握手

雷人

路过

鸡蛋

相关阅读

最新评论

热门频道

  • 大数据
  • 商业智能
  • 量化投资
  • 科学探索
  • 创业

即将开课

 

GMT+8, 2020-7-11 20:33 , Processed in 0.116574 second(s), 27 queries .