Fast Randomized SVD-白红宇的个人博客

Fast Randomized SVD

发布日期：2021-06-30 15:15:55 浏览次数：3 分类：技术文章

本文共 2787 字，大约阅读时间需要 9 分钟。

一、简介

标题可译为快速随机奇异值分解，单纯觉得念得拗口，故标题未做翻译。之前看过一点相关内容，当时对这个方法还谈不上理解，随着相关文献看的越来越多，理解也就逐渐加深了。当然，涉及到Terry Tao的地方我没有花大量的时间去研读，所以假设我就知道了。今天下午先不谈奇异值分解与其他方法的联系，只是总结一下我对这个方法的理解。事实上，有很多方法可以计算矩阵的奇异值分解，下述内容利用主流的

随机思想来计算矩阵的奇异值分解。

二、符号标定及基本概念

文中各矩阵维度: 输入A(m*n)，随机矩阵Ω（n*l），前面两者的乘积矩阵Y（m*l），QR分解得到的矩阵Q（m*l）,R（l*l）

The range of A:英文中这么一个概念，实际上就是列空间的意思，即由矩阵A的列向量张成的空间，参照wiki：这个概念没什么好吓人的

正交矩阵：A的转置乘以A等于A乘以A的转置等于单位阵，则A称为正交矩阵。正交矩阵的逆矩阵等于正交矩阵的转置。

QR分解：矩阵分解成两个矩阵的乘积QR，其中Q是一个正交矩阵，R是一个非奇异的上三角矩阵。

线性代数的一点小trick：A的转置的逆矩阵等于A的逆矩阵的转置，这一个很容易证明不再啰嗦了。AB乘积的转置等于B的转置乘以A的转置。

交代了这几点，下面叙述应该不会存在什么问题了。

三、算法理解

算法主要分为两个步骤：1.利用随机技术计算A的列空间的一个近似Q，使得Q满足有r个正交列(r较小)且A近似等于Q*Qt*A(Qt表示Q的转置) 2.得到Q利用Q计算A的奇异值分解

在给定Q的情况下，构建矩阵B=QtA，由于Q只含有少量的列，因此Q的“体积”相对较小，其奇异值分解相对容易计算，不妨记作B=S∑Vt，由前面简介A=Q*Qt*A=Q(Qt*A)=Q*B=Q(S∑Vt)=QS∑Vt=(QS)∑Vt，容易证明QS为正交阵，不妨迹QS=U，从而得到了A的奇异值分解A=U∑Vt

这个算法的小trick来自于近似矩阵Q是可以高效计算得到的！（说的容易，理解起来要慢慢来）

直觉上，要去估计矩阵A的列空间，我们可以随机取一系列的向量Ω1，Ω2，Ω3...然后检查由A与这些向量作用的结果张成的空间（翻译的比较拗口，后面会说到如何理解），不妨将随机选取的向量组成的矩阵记作Ω，然后计算一个矩阵Y=AΩ，然后对Y进行QR分解得到Y=QR，然后Y就可以看成由Q的列向量张成的，即Q可以看成Y的列空间的正交基。

翻译到了这里到底怎么理解呢？为什么QR分解得到的这个Q就可以看成我们最初希望寻求的那个Q呢？注意到，前面文中有两个关于Y的公式，把这两个式子放到一起比较一下就相对容易理解了

Y=AΩ

Y=QR

第一个式子中，Y可以看作由A的列向量张成的，那在第二个式子中，Y又可以看成由Q的列向量张成的，这是不是可以说Q是A的列空间的一个近似了呢？而且看维度都是m维的，为了方便理解，下面给出一个简陋的例子，比如说

Y=[3 0 0;0 3 0;0 0 3]（3*3），那么Y可以分解成两个矩阵的乘积，分别为A=[1 0 0 0;0 1 0 0;0 0 1 0](3*4)，Ω=[3 0 0;0 3 0;0 0 3;0 0 0](4*3)(这里我故意分别多写了一行和一列)，对Y进行QR分解得到Q=I3（3阶单位阵）*Y(这个例子比较特别，但是可以看成一个QR分解)，可以发现A与I3是相似的，仅仅一列不一样而且是一个零列，因此我可以说Q是A的列空间的一个近似，且Q含有少量的正交列，是不是就满足了一开始说的Q需要满足的第一个条件了呢？（btw，这个例子不太好，应该找一个列很多的矩阵来做分解但是手工不容易构造）

捋一下算法流程吧

1.生成一个高斯随机矩阵Ω(n*l)

2.构建一个m*l维的样本矩阵Y=AΩ

3.对Y进行QR分解得到m*l维的正交矩阵Q

4.构建一个l*n维的矩阵B=Qt*A

5.计算小矩阵B的奇异值分解B=S∑Vt

6.令QS=U得到A的奇异值分解A=U∑Vt

我自己也尝试着实现了一下该算法，不贴我自己实现的了，贴一下从网上找来的代码，方便群众，代码所有权归原作者所有，链接在这里：。无意侵权，如有侵权，可联系jzwang@bjtu.edu.cn，马上删掉！代码如下

function [U,S,V] = rsvd(A,K)%-------------------------------------------------------------------------------------% random SVD% Extremely fast computation of the truncated Singular Value Decomposition, using% randomized algorithms as described in Halko et al. 'finding structure with randomness%% usage : %%  input:%  * A : matrix whose SVD we want%  * K : number of components to keep%%  output:%  * U,S,V : classical output as the builtin svd matlab function%-------------------------------------------------------------------------------------% Antoine Liutkus  (c) Inria 2014[M,N] = size(A);P = min(2*K,N);X = randn(N,P);Y = A*X;W1 = orth(Y);B = W1'*A;[W2,S,V] = svd(B,'econ');U = W1*W2;K=min(K,size(U,2));U = U(:,1:K);S = S(1:K,1:K);V=V(:,1:K);

下面第二个问题是这样求得的Q满足A近似等于Q*Qt*A吗？答案是满足的！因为B=QtA，所以A=QB=QQtA，也就是说这样所构建的Q是符合我们开始时候所期待的！

参考：

1.https://en.wikipedia.org/wiki/QR_decomposition

2.http://arxiv.org/abs/0909.4061

3.https://en.wikipedia.org/wiki/Row_and_column_spaces

4.https://research.facebook.com/blog/fast-randomized-svd/

转载地址：https://jianzhuwang.blog.csdn.net/article/details/51791695 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：最大连续子序列

下一篇：visio插入公式另存为出现斜方框

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

一、简介

二、符号标定及基本概念

三、算法理解

发表评论

最新留言

关于作者

推荐文章