AMM：一种快速、准确、鲁棒的矩阵乘法算法及并行实现

ðÞqPkqPk k kF12 2 2¼1/12*通讯作者。2XXω1/1沙特国王大学学报一种实用的流式近似矩阵乘法算法蒂娜山口FrancisSaud，Kumudha Raimond印度泰米尔纳德邦哥印拜陀Karunya技术与科学学院计算机科学与工程系阿提奇莱因福奥文章历史记录：2018年6月21日收到2018年8月14日修订2018年9月9日接受在线发售2018年保留字：近似矩阵乘法矩阵素描常见方向素描大数据A B S T R A C T近似矩阵乘法（AMM）已经成为一个有用的和计算成本低廉的大型矩阵的实际乘法的替代。在过去，AMM提供了随机和确定性的解决方案。最新的工作提供了一个确定性的算法，解决AMM更准确地比其他作品。它是一种既快速又准确的流算法。但是，它对噪声的鲁棒性较差，并且在输入矩阵中存在概念漂移的情况下也容易具有不太理想的性能。我们提出了一种算法，该算法更准确，对噪声具有鲁棒性，对数据中的概念漂移具有不变性，同时具有与最先进算法几乎相同的运行时间。我们还证明了所提出的算法的理论保证存在。实验结果表明，该算法的性能比原算法提高了90%.我们还提出了一个总体框架用于并行化所提出的算法。该算法的两个并行版本实现了高达1： 9倍和3： 6倍的加速比，在原始版本的算法。©2018作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍在大数据场景中，人们经常会遇到非常大的数据集。通过大，我们的意思是矩阵具有大量的属性或大量的实例，或两者兼而有之。它们通常以实时数据流的形式提供，或者分布在不同的机器上，甚至可以是两者的组合。大矩阵的乘法在k均值聚类中有应用（Bendridis等人，2015;Cohen等人，2015 a），信息检索（Eriksson-Bique et al.，2011）、图像处理（Madrid等人，2012）、典型相关分析（Golub和Zha，1995）。为了获得这种乘法的精确结果，将需要多项式运行时间。对于两个大小为m1×d和d×m2的矩阵，是O m1m2d。这并不总是可行的，因为实例或者属性可以是任意大的，因此计算成本太高。AMM是解决这个问题的一个时间效率高的解决方案。AMM的结果是实际矩阵的近似产品，理想情况下不应与实际产品相差太多AMM在流数据设置中变得更具挑战性。数据矩阵一次到达几行或几列。由于矩阵的巨大尺寸，不再可能将整个矩阵存储在内存中。为了讨论AMM的相关工作和挑战，首先需要一个正式的定义。在正式定义AMM问题之前，我们介绍了全文中使用的符号。1.1. 符号在整个文本中，我们使用粗体字母表示矩阵，粗体字母表示向量。我们把一个具有m个实例和d个属性的矩阵记为X2Rm×d.向量x的欧几里得范数定义为xd X2. 的i¼1i矩阵的Frobenius范数定义为Xmx和j¼谱范数被定义为r1<$x1，其中r1表示最大sin。X的值。迹范数定义为k X k ¼Pm R1，以及电子邮件地址：deena. gmail.com，deenapf@karunya.edu.in（D. P. Francis），kraimond@karunya.edu（K. Raimond）。沙特国王大学负责同行审查1/4 k kω=k k2。简化的Singu-X的最大值分解（SVD）得到三个矩阵URm×mRd×m和RRm×m，使得XUR VT。矩阵U和V是酉矩阵，分别包含左奇异向量和右奇异向量。 矩阵R 包含单数价值观，frigm沿着对角线，r1pr2p... PrmP0. 的https://doi.org/10.1016/j.jksuci.2018.09.010矩阵的稳定秩p定义为k×kF。k×k21319-1578/©2018作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com核范数定义为l1456D.P. Francis，K.Raimond/ Journal of King Saud Universityð ðÞÞðÞðÞDe2ðÞ¼ ðÞð ðÞÞ¼ ðÞ现在我们正式定义AMM问题。问题1（AMM）。给定两个大整数找到一个矩阵Z0使得对于给定的范数c，kXYT-Z0kc是小的。表1算法与已有算法的比较。工作t约束注意到Drineas等人0 3 .第一次世界大战（2006）第二次世界大战（2006）基于投影图1描述了AMM的基本思想。这里，Z是矩阵X和Y的实际乘积。在这种情况下，大维度的大小d被缩减为t。Z0是矩阵X0的乘积02 The Dog（2009）03 The Dog（2011）Os-2F随机投影基Xps-2log m1m 2m基 于 S采样和Y0，它们是原始矩阵的近似值自己Kyrillidis等人（2014年）xls-2S随机投影基1.2. 贡献Cohen等人（ 2015 b）X k log 1 =ds-2;S-2战斗机S随机投影基这项工作的主要贡献概述如下。提出了一种准确、鲁棒的流AMM算法b-Cooccurring所提出的算法承认一定的理论保证，证明在这项工作中。实验分析所提出的算法，以证明其改进比以前的作品。通过实验证明了所提出的算法的并行化的好处。这项工作安排如下。在第二节中，讨论了AMM的前期工作。所提出的算法，它的运行时间和理论保证在第3节中讨论。实验见第4节。在第5节中讨论了所提出的算法的并行化。在第6节中，通过实验获得的主要结果进行了讨论。结论见第7节。2. 以前的作品大矩阵的操作发生在推荐系统中（Bachrach和Porat，2013），大图像的处理（Yu例如，2018; Alsmirat等人，2018），物联网系统（Yaseen等人， 2017）和网络安全（Gupta等人，2016年）。在过去，已经提出了许多AMM的解决方案。我们讨论了这些工作，详细介绍了他们的基本思想，保证，时间复杂度和缺点。以往工程与拟建工程的比较见表1。这里，第三列表示算法所满足的理论界的类型。用S表示谱范数界，用F表示Frobenius范数界。一般来说，所有算法都试图减少Ye etal. （2016）s-1SFD basedMrouehet al. （2017年）O.s-1ppXpYSFD为基础，O.s-1ppX pYSb-基于FD行/列（取决于哪个更大）。例如，如果d对于两个输入矩阵都很大，则算法用小得多的数字t;td替换d。<如果我们要将两个大小为m1×d和m2×d的矩阵相乘，那么运行时间将为0m1m2d。通过使用AMM算法，这种复杂度可以降低到Om1m2t.此后，我们使用s（通常为s1）<表示近似算法的误差参数Drineas等人（2006年）提供了使用采样的AMM溶液。在他们的方法中，t列从两个输入矩阵中采样。通过设置tXs-2，他们提供了Frobenius范数保证，T恤它们还通过根据列的杠杆分数对输入矩阵的条目进行采样来提供谱范数方面的保证。基于随机投影的AMM解决方案首先由Sarlos（2006）提供。在此方法中，输入矩阵乘以矩阵RRt×d，从满足不经意Johnson-Lindenstrauss（JL）保证的分布中提取。通过将t设置为Os-2log 1=d（Johnson和Lindenstrauss，1984），得到了以Frobenius范数形式给出克拉克森和伍德拉夫（2009）提供了另一种使用符号或拉德马赫矩阵计算AMM解的方法。通过设定t为Os-2，给出了Frobenius范数的界.为了加速RX的计算，可以求助于Ailon和Chazelle（2009）、Ailon和Liberty的作品中的思想。（2013）、Krahmer和Ward（2011）、Nelson等人（2014）。基于输入稀疏时间的快速JL解决方案由Clarkson和Woodruff（2013）以及Nelson等人提供。（2013年）。Fig. 1. AMM的基本概念●●●●D.P. Francis，K.Raimond/ Journal of King Saud University145722¼ ðÞ2¼ ðÞL9：B¼0URð Þ2¼ ðÞÞ¼.pL1L¼Magen和Zouzias（2011）使用随机采样程序提供了两种解决方案。结果表明，利用这两种方法，乘性谱范数的保证以很高的概率存在.第一种方法是将输入乘以矩阵的随机符号矩阵RRt×n，其中t n。在第二种方法中，对输入矩阵中的t行进行采样根据概率，pkXik2 kYik2. 在这两起案件中，223.1. 预赛FD：FD算法用于以流式方式找到矩阵由输入矩阵A2Rm×d构造草图矩阵B2Rm×l.算法1 FDiPnkXikYik故障概率最大为1聚丙烯酸和1：输入：1;ARm×dM Lt<$Xps-2logm1m2，其中p是稳定秩，定义为p<$pXp Y。对维数（m1和m2）的依赖性也被p代替，因此tXs-4p。注意第一方法是数据不经意的，而第二个不是。前一项的不希望的对数m1m2m和s-4项2：B← 0×3：对于i一...... 会做4：将A列插入B5：如果B没有零值列，则6：½U;R;V]¼svdBKyrillidis等人（2014）将算法替换为l、总核等级和s-2。总核级被定义 为 1/4lXlY 。他 们 的 方 法 是 将 输 入 矩 阵 乘 以 矩 阵G2Rt×n;G~N<$0;1=t<$。谱范数保证，得到tXls-2。以前工作的一个问题是核级瓜尔豆-7：d ¼r28：R0¼qR2-dl10：如果11：结束12：返回Bantee被认为比稳定等级保证弱这是因为，l X> p。 Cohen等人（2015 b）后来表明，可以在不诉诸于核等级。他们的方法是将输入矩阵与矩阵RRt×n相乘以获得谱范数保证。在第一种方法中，该矩阵R可以是由下式得出的矩阵：不经意子空间嵌入（OSE）的分布。t的值被设置为t1/4Xklog 1=dks-2。在第二种方法中，t被设置为tXks-2 ，并且R被选择为使得某些确定性-的条件得到满足。上述所有方法的缺点是，当参数t的值小时，随机化算法失败。第一个确定性的解决方案AMM提出了叶等。（2016年）。他们的方法包括使用称为Frequent Directions（FD）的矩阵草图绘制算法（Liberty，2013）创建输入矩阵的草图、BX和BY。 谱范数保证是由这个算法提供的。我们将此算法称为FD-实验结果表明，该算法比其他矩阵绘制算法具有更好的性能。它还可以处理具有概念漂移的数据。FD在流式异常检测（Huang和Kasiviswanathan，2015; Francis和Raimond，2018 b）、流式内核主成分分析（Ghashami等人，2016;Francis和Raimond，2017），在线散列（Leng等人，2015）和流谱聚类（Yoo等人， 2016年）。b-FD：它是FD的一个更健壮和准确的版本。在算法1中，第8行由ReduceRank过程（算法2）代替。这确保了奇异值的减少以可变的方式发生，从而给出每个奇异值一种直观的区别对待。衰减（）定义如下，其中k 1/4 0;. ; l-1; b 2 ≤ 0;1 μ m.KB嗯。算法的参数是草图尺寸l，衰减eb;k;lel-1-1ð1Þ设为Ls-1条件下eb-1后来，Mürdoueheetal. （2017）提出了一个更快的修改版本关于FD-AMM通过设置l/4Os-1pXpvpY，他们的方法可以实现乘性光谱误差保证。我们将其算法称为Cooccurring-AMM。如前所述，当t较小时，随机化算法具有较高的失败概率。后来提出了确定性算法来避免这个问题，并提供更强的保证。它们基于FD的直接修改，这比其他变体更不稳定。事实上，Mroueh等人（2017）将鲁棒性作为一个开放问题。在这项工作中，我们提出了一个更强大和准确率确定AMM算法。为了实现鲁棒性，我们将FD的鲁棒和准确的变体称为b-FD，由Francis和Raimond（2018）提出。对于AMM任务，我们证明了强有力的理论保证，并通过实验进一步证明了我们的方法的有效性。3. 该算法在描述所提出的算法之前，介绍了两个初步的算法。算法2ReduceRank（R;b）d ¼r2R0¼直径g. qr2-atenuateb;0;ld;.. . ;qr2-atenuateb;l-1;ld返回R0b-FD算法的基本思想如图所示. 二、在这里，B i表示第i批结束时的草图矩阵，其中i 1; 2;. ;d=1。同现-AMM算法使用FD的修改版本，其不如其变体稳健特别地，b-FD变体显示出比FD更稳健。FD的降低秩步骤（算法1中的第8行）同等地降低所有奇异值，而在ReduceRank（算法2）中，变量在奇异值上进行缩减。由于这种变量减少，数据中的噪声被更好地减少。 b-FD算法可以被合并到Cooccurring-AMM中，以提高其鲁棒性。1/11458D.P. Francis，K.Raimond/ Journal of King Saud UniversityY不ffiffiffi←XXp←XX22LL=2图二. b-FD的基本思想。算法3b同现-AMM得到矩阵QX; RX; QY; RY。l×l矩阵的SVD然后计算RXRT。使用算法4，约简矩阵R~输入：X2Rm1×d; Y2Rm2×d;l2R;b2 0;1输出：BX2Rm1×l; BY2Rm2×l对于i2½1;.. . ;d]做BX ½：;i] ←X½：;i]BY ½：;i] ←Y½：;i]如果BX和BY具有l个非零列，则½QX;RX] ←qrBX半QY;RY] ←qrBYU;R;V] ←svdRXRY得出最后，分别用乘积QXUp<$R~∞和QYVp<$R~∞更新草图矩阵.算法4参数化ReduceRank（R;l;b）d←rl=2R01/4直径最大值xr1-d衰减系数eb;0;l;0g;。 . . ;最大值frl-d衰减振幅b;l-1;l; 0g返回R0CQUpRCY←QYVpR只为证明R0¼参数化减少RankR;l;bBQUr10的BY←QYVpR0end if结束返回BX; BY3.2. 该算法该算法通过逐列读入输入矩阵的列来构造草图矩阵BX和BY，使用类似于共生AMM的步骤。主要的区别是，而不是简单地使用奇异值的中值来阈值的输出中的噪声水平，我们纳入了鲁棒性为 了 做 到 这 一 点 ， 稍 微 修 改 ReduceRank 过 程 以 获 得 参 数 化ReduceRank（算法4）。 可以注意到 ，d 的值是rl=2而不是r2（如在ReduceRank中）。完整算法如算法3所示。首先，草图矩阵BX和BY分别填充有X和Y的l列。然后，计算它们的QR分解，而不是对草图矩阵这3.3. 复杂性分析3.3.1. 时间复杂度该算法每次读入矩阵X和Y的每一列，直到草图矩阵BXRm1×l和BYRm2×l被填充。然后计算草图矩阵的qr分解这两个qr分解分别需要O<$m1l2时间和O<$m2l2时间。活泼地 然后，计算了RX R YT的SVD。 这需要时间Ol3，因为RX R YT2 Rl×l。ParameterizedReduceRank过程将R的值中的l=2个减少到零。因此，qr和SVD计算每隔d= 101=200步进行一次然后是形成草图矩阵BX和BY的问题，它们分别需要Om1l2和Om2l2那么，的总时间采取是Od m1l2m2l2l3m1l2m 2l2l 1m1 l2m2l2 l2m。3.3.2. 空间复杂度我们需要将草图矩阵存储在内存中，这需要O<$m1l<$m2l<$m空间。在此外，我们需要到存储QX; RX; QY; RY。这需要一个额外储存Om1ll2m2ll2lOmlm ll2l。矩阵U、 V和RD.P. Francis，K.Raimond/ Journal of King Saud University1459XY2j¼0¼ ð ð Þð ÞÞ不我i;T我i;T我i;T启ðÞXY2XXI¼我- kk其中UY~N<$0;1< $2Rn×ky;R2Rky×ky，1/4Xr-r~j我ω221/4Xr-衰减的r b;j;ld也需要储存，这就需要储存Ol2。因此，所需的总空间为Om1lm2l l2。3.4. 理论保证在本节中，我们证明了与Mroueh et al.（2017）类似的保证适用于所提出的算法。设Ci; Ci所有算法的5次运行。协方差误差的谱范数的值即使在算法的多次运行之后也保持不变，因为被比较的所有算法都是确定性的。实验中使用的输入矩阵有三种类型：低秩无噪声，低秩噪声和突然和重大概念漂移的数据。低等级建筑背后的原因XY矩阵是为了证明矩阵的秩对表示第i次迭代结束时的CX和CY的值，算法的错误。 正如Mroueh等人所观察到的那样。（ 2017年），循环。 同样，设Bi-1Bi-1表示BX在FD-AMM的情况下，XYT的最佳秩k近似和BY在的端的的第一次迭代让gb;l¼Pl-1衰减型β b; j; lβ。那么，下面的引理为真。引理1. gb;l6l定理1.在应用算法3之后获得的矩阵BX和BY服从以下界限。kXYT- BX BYk 6 kXkFk YkF=l2证据证明是类似的一个在Mroueh等人。（2017年）。在出现r~ i的表达式中出现差异。我们有对于共现- AMM，lminrankX; rank Y。因此，对于较小的l值，后者比前者获得更好的精度。类似地，对于b同现AMM，对于较小的l值获得较低的误差，如4.5节所示。编程是用Python和所有的exper-在具有1.7GHz Intel Core i3处理器和4GB RAM的Linux机器中执行这些任务4.2. 设计输入矩阵X和Y的每一列被馈送到三个流算法。然后获得相应的草图，并使用下面定义的指标进行性能评估（第4.3节）。对于所有算法，参数草图尺寸l是固定的对于所有矩阵，我们取l小于d的大小（X和n nkBX BTk¼XkCiCiCi;Tk-kBi-1Bi-1;Tk-XkCiCiCi;Tk-kBiBi;TkY）。为了研究误差的变化，Yω1/1XYωX Yω1/1XYωXYωð3Þ对于L值的固定集合运行算法对于统一随机、低秩和噪声低秩输入矩阵，l值在100到1000之间变化。对于漂移输入矩阵，L值-我们还有，UE的范围从100到500。这是因为d的最大值kCXCYkωBi-1X Yω6 kXi YTk k Xik YikL-1ð4Þ对于这些类型的矩阵是500。在实践中，期望固定小于d的l的值。这样做是为了减少运行-kCXCYkω — kBX BYkω我我Jj¼0L-1宁时间。为了确定b的最佳值，所提出的算法针对b的多个值运行，并且28的值是被认为是最佳的。对于所提出的算法，b的值为：i我我jJj¼01/4lg/b;lg/dPldi5第二个等式是由于r~ji的定义，最后一个不等式是由于引理1。合并等式（3）设置为28（Francis和Raimond，2018a）。4.3. 性能度量为了比较所提出的算法与其他算法的性能，使用以下度量。● 协方差误差S的谱范数：它的测量方法如下。SXYT- BX BTk27当l/s-1ppxpppyp p p X p ppTT¼kYkXY- B Bk 6skXk k Ykð6Þ计算近似矩阵乘积。4. 实验4.1. 设置由于共生AMM已经被证明具有优越的性能相比，其他以前的算法，我们不重复他们的结果在这项工作中。相反，我们证明了所提出的算法b同现AMM的性能，通过比较它与同现AMM和FD-AMM。我们还包括FD-AMM，因为它是一个算法-基于FD.为了完整性，还提供了与基线算法的时间比较基线算法计算XY T¼Pd1X i Y T。该算法的运行时间为Om1m2d，4.4. 输入矩阵矩阵X和Y是使用不同的过程生成的，每个结果都相应地命名● 均匀随机：生成一个大小为2000 × 10000的随机矩阵和另一个大小为1000 × 10000的随机矩阵，其条目从1/2 0;1μ m随机均匀抽取。● 低秩矩阵：Ghashami等人的程序。（2014年）使 用 生 成 无 噪 声 低 秩 矩 阵 。 X¼URVTT ， 其 中UX~N<$0;1< $2Rn×kx;R2Rkx×ky，其条目是<$Rjj<$^1-j- 1=kx;VX2Rmx×kx是酉矩阵。Y¼TT所需空间为O m1m2。这个算法产生的错误-Rithm总是零，因为它计算精确的矩阵乘积。在第4.5节中，取平均值后报告计时结果是1-j-1;VY2Rmy×ky是酉矩阵.以下所有这种类型的矩阵都有m11/41000;m2/4 2000;d/4 5000。2我1460D.P. Francis，K.Raimond/ Journal of King Saud University¼¼ ¼¼- 无噪声Randl：通过设置kx^ky^400，使用上述过程构造X和Y- 无噪声Rand 2：使用上述过程构造X和Y通过设置kx<$400;ky< $40，- 无噪声Rand 3：通过设置kx/40;ky/ 40，使用上述过程构造X和Y噪声低秩矩阵：构造低秩矩阵类似于上面给出的过程，但添加了高斯–Noisy漂移：构造具有漂移的矩阵的过程取自Ghashami等人。（2014年）。计算两个随机向量x和y在两个正交子空间M和N上的投影我们有，M2Rm1; N2Rm2，和m1 1/4 400，M2四、该矩阵被构造为归一化投影向量，使得x在M上的投影噪声 X<$URV T<$T<$N=g，其中g>0且N~N<$0;XxXxxX出现在y在N上的投影之前。由于该施工程序，该数据具有重大和突然的漂移两个矩阵-类似地，Y1/2RVTTN=g，其中g>0。所有以下内容-YY Yyy这种类型的ING矩阵具有m11000;m2 2000;d5000。–Noisy–Noisy构建了10000 × 500的CEs。4.5. 结果图3中的曲线图显示了协方差误差随算法草图大小的变化。如前所述，我们不包括图三. 各种数据矩阵的协方差误差随算法草图大小的变化。不包括基线算法，因为其误差始终为零。●●D.P. Francis，K.Raimond/ Journal of King Saud University1461基线算法的误差，因为它对所有的l值都是零误差。 从图 3（a）中，可以观察到，对于几乎所有草图尺寸，所提出的算法的误差都低于先前的两种算法。对于较大的l值，即对于lP800，b共现AMM和共现AMM是一样的 图 3（b）和（c）表明，b共存AMM和共存AMM可忽略不计。在FD-AMM的情况下，观察到误差值的波动在噪声数据集的情况下（图）。 3（d）-（f）），b共现-AMM对于几乎所有的l值始终实现较低的误差值。这证明了所提出的算法的鲁棒性，如前所述。 对于数据集均匀随机（图。（第3（g）段）共现AMM和FD-AMM实现了几乎相似的类型突然和主要的概念漂移，再次提出的算法是明显的赢家。这证明了它可以处理漂移更有效地与以前的算法相比。接下来，我们比较算法所需的时间。 所用时间随草图尺寸的变化如图所示。 四、可以观察到，基线算法总是（对于所有数据集）具有最大的时间，而bCoccurring-AMM和Coccurring-AMM具有几乎相同且最少的运行时间。为了证明b同现-AMM与同现- AMM相比所带来的改进量，我们计算误差减少的百分比。该值计算如下。所有l值的误差值。b同时发生-AMM是明确的减少误差错误C-错误Cb这个数据集的赢家 在漂移数据集（图。（3）（h），占总人口的百分比误差Cω100见图4。各种数据矩阵的算法所花费的时间。1462D.P. Francis，K.Raimond/ Journal of King Saud University≤S这里，errC和errCb分别是由共存AMM和b图5中示出了所提出的算法相对于共现AMM的误差减少百分比的曲线图。在几乎所有的情况下，b共现AMM保持一个良好的百分比减少错误共现AMM。对于非噪声Rand1（图5（a）），所提出的算法的改进百分比保持增加，直到草图大小=800，之后没有改进。在无噪声Rand2和无噪声Rand3的情况下（图5（b）、（c）），两种算法的性能几乎相似。在Noisy Rand1的情况下（图5（d）），所提出的算法在草图大小= 100时表现出近26%的改进。在图5（e）和（f）中，对于小草图尺寸，（1200），近90%的改进，共现AMM。在均匀随机（5（g））的情况下，性能算法的有效性随着草图尺寸的增大而增大。 图 5（h），可以观察到，误差减少的百分比对于较小的草图尺寸，大于70%，并且随着草图尺寸的增加，减少错误的百分比会降低。5. AMM的并行计算可以并行运行结果将具有与非并行化情况相同的理论保证这是可能的，因为FD 算法及其变体b-FD是可并行的（Liberty ， 2013;Francis和Raimond，2018 a）。parallelization的优点是运行时间可以减少一个因子s，其中s是运行的算法实例的数量。ning 并 行 。 因 此 ， 并 行 化 的 b-Cooccurring-AMM 的 运 行 时 间 为Odm1lm2ll2m。因此，如果s为1/4 2，我们可以预期通过并行执行获得近2：0倍的加速。如果实例图五. 对于不同的数据矩阵，所提出的算法比共现AMM的改进百分比。D.P. Francis，K.Raimond/ Journal of King Saud University1463第1页第1页X12XXXYYYPY在同一系统中并行运行，则我们不需要考虑通信复杂度，相反，我们只对时间复杂度感但在数据物理分布在不同机器上的情况下，算法的通信复杂性更为重要。在下面的部分中，我们讨论用于并行运行b共存AMM的一般框架。5.1. 一个总体框架对于任何矩阵X1/4/2X1;. . ;Xs] 2Rm1×d， 其中每个得到了B0X和B0Y两个谱带。这两个矩阵等价于全局草图BX;BY（Liberty，2013）。5.2. 实验在这一部分中，通过实验验证了上述框架中给出的加速比保证。我们比较了所提出的算法和它的并行化版本5.2.1. 设置比较的算法是并行bCoccurring-AMM算法Xj2Rm1×dj;Psdj¼d。类似地，对于Y1/2/Y1。 . . ;Ys] 2Rm2×d，其中缩写为P-b-AMM和b共现-AMM，缩写为每个Xj2Rm2×dj;sdj¼d。平行框架的基本思想如图所示. 六、在树的最低级别中，为了得到草图矩阵对，可以对形式为<$Xj;Yj< $的输入矩阵并行执行b同现AMMb-AMM。在实验中，我们使用5.1节中描述的框架。特别地，我们使用图6中给出的设置。每个输入矩阵被分成一定数量的块。这种划分是沿着矩阵的维度d进行的的细节块大小= 2的并行算法详细示于图2中。7.第一次会议。J JBX; B Y 在树的下一级中，执行级联步骤，随后执行b个同现AMM的s=这里，具有相同原点矩阵的一对矩阵的草图是聚集在一起。例如，将B1与B2级联（按列）以获得1/2B1;B2]，并且将B1与B2级联以获得B;B]，等等。那么，s=2个b同现-AMM的实例是在所有这样的草图矩阵对上并行执行这个过程在树的每一级上继续，直到最后的草图矩阵。我们使用符号P-b-AMM（p）来表示所提出的算法的不同类型的并行版本这里p是每个矩阵被分割成的块的数量，也是块的数量。b-AMM的并行执行的BER。例如，P-b-AMM（2）涉及将矩阵X和Y分成两个块，因此，并行运行b-AMM的两个实例（图11）。 7）。我们改变了块的数量，并显示了在与原始版本兼容时获得的加速比在图1中的树的级别中的每个b-Coccurring-AMM。 六是并行运行。因此，在图7（块大小= 2）的情况下，图的最左边部分上的两个b-AMM并行运行。的包括B1和B2以及B1和B2的串联步骤，X X Y Y也是平行进行的。由于低秩矩阵（噪声和非噪声）都具有相同的大小，因此我们选择其中一个进行此实验。因此，算法在三种类型的输入矩阵上运行：无噪声Rand1，均匀随机和漂移。表2P-b-AMM（p）和b-AMM对于1/4100的定时比较输入矩阵类型算法所需时间（s）无噪声-Rand 1b-AMM 5.4716P-b-AMM（2）2.8675P-b-AMM（4）1.5928均匀随机b-AMM 11.0337P-b-AMM（2）5.6970P-b-AMM（4）3.0537漂移b-AMM 3.7113P-b-AMM（2）1.9495P-b-AMM（4）1.0326见图6。共现-AMM。见图7。 P-b-AMM（2）的详细信息1464D.P. Francis，K.Raimond/ Journal of King Saud University见图8。对于不同的l值，所有三种算法的时序结果。5.2.2. 结果表2显示了草图尺寸= 100时，针对三种输入矩阵的两种算法所花费的时间。在无噪声Rand1的情况下，矩阵为大小1000× 5000和2000×5000时，P-b-AMM（2）相对于b-AMM实现了1： 9倍的加速比，而P-b-AMM（4）实现了3： 4倍的加速比。对于大小为1000× 10000的均匀随机矩阵，P-b- AMM（2）和P-b-AMM（4）分别获得了1： 9倍和3： 6倍的加速比.对于10000× 500的漂移矩阵，P-b-AMM（2）和P-b-AMM（4）的加速比分别为1：9 x和3：6x. 图中的图。 8显示所用时间的变化草图尺寸。网格化提高了所有草图大小的加速比。6. 讨论从第4节给出的第一组实验的结果可以得出以下推论。b-Coccurring-AMM在有噪声和无噪声的数据集上同样表现良好。根据结果，所有算法都表现出以下行为。草图尺寸越大，获得的误差越小。该算法实现了较低的错误比以前的算法小的草图尺寸。这在几乎所有的图表中都可以观察到（图3）。因此，所提出的算法实现了更低的误差比其他更快的所有类型的输入。例如，对于草图大小= 100，所提出的算法产生300的误差，而其他算法对于非噪声Rand1和噪声Rand1产生近400的误差（图11）。 3（a）和（d））。当矩阵与突然和主要漂移（漂移数据集）相乘时，该算法实现了比其他算法更低的误差这表明该算法在处理输入矩阵的突然和重大漂移的有效性。关于由所提出的算法实现的误差减少的百分比，可以进行以下观察在大多数情况下，观察到的趋势是，随着草图大小的增加，建议和以前的误差之间的差异变得接近。这意味着，对于大的草图尺寸，这两种算法实现类似的性能。在均匀随机的情况下观察到一个例外，其中所提出的算法随着草图尺寸的增大而增大。这证明了所提出的算法的有效性，同时表明以前的算法无法产生准确的结果，这样的矩阵。第5.2.2节中获得的结果表明，● 根据第5节，预计P-b-AMM（2）和P-b-AMM(4)与b-AMM相比，实现了近2： 0倍和4：0倍的加速比。实验结果表明，对于所有输入矩阵。所提出的算法受益于采用并行化在一个显着的方式。即使是大的草图尺寸也可以使用，而不会花费太多时间，如图所示。8.第八条。7. 结论过去已经提出了AMM问题的随机和确定性解决方案Coccurring-AMM是一种确定性算法，被证明是更快，更准确的比以前的算法。我们提出了一个更准确，鲁棒性和快速的算法称为b同现AMM。我们提供了理论上的保证和实验结果证明其效率和有效性实验结果表明，高达90%的改善，比以前的方法是使用所提出的算法，即使使用一个小的草图尺寸。我们也提供了一个通用的框架，用于并行化所提出的算法。两个并行版本实现了显着的加速比高达1： 9倍和3： 6倍的算法。致谢作者要感谢印度政府电子和信息技术部（MeitY）根据数字印度公司实施的Visvesvaraya电子和信息技术博士计划引用Ailon，N.，Chazelle，B.，2009.快速johnson-lindenstrauss变换与近似近邻法。SIAMJ. Comput. 39（1），302-322。Ailon，N.，利伯蒂，E.，2013.一种几乎最优的无限制快速johnson-lindenstrauss变换。ACM Trans. 算法（TALG）9（3），21。●●●●●●D.P. Francis，K.Raimond/ Journal of King Saud University1465Alsmirat，M.A.，Al-Alem，F.，Al-Ayyoub，M.，Jararweh，Y.，古普塔湾2018.数字指纹图像质量对指纹识别准确率的影响。多媒体工具应用，1-40Bachrach，Y.，Porat，E.，2013.使用快速伪随机指纹的大数据推荐系统草图。自动机、语言和编程国际研讨会。施普林格，pp. 459-471Becludis角，Zouzias，A.，马奥尼，M.W.，Drineas，P.，2015. k-means聚类的随机降维。IEEE Trans. Inf. Theory 61（2），1045-1062.克拉克森，K.L.，伍德拉夫，D.P.，2009.流模型中的数值线性代数。在：第四十一届年度ACM计算理论研讨会论文集。ACM，pp. 205-214克拉克森，K.L.，伍德拉夫，D.P.，2013.输入稀疏时的低秩逼近与回归。在：第四十五届年度ACM计算理论研讨会论文集。ACM，pp. 81比90Cohen，M.B.，Elder，S.，Musco，C.，Musco，C.，Persu，M.，2015. k-means聚类和低秩近似的简化。在：第四十七届年度ACM计算理论研讨会ACM，pp.163-172.Cohen，M.B.，Nelson，J.，伍德拉夫，D.P.，2015.关于稳定秩的最佳近似矩阵积arXiv预印本arXiv：1507.02268。Drineas，P.，Kannan，R.，马奥尼，M.W.，2006.矩阵的快速蒙特卡罗算法i：近似矩阵乘法。SIAM J. Comput. 36（1），132- 157。Eriksson-Bique，S.，Solbrig，M.，Stefanelli，M.，Warkentin，S.，阿比河， Ipsen，I.C.，2011年。蒙特卡洛矩阵乘法算法的重要抽样及其在信息检索中的应用。Siam J. Sci.Comput. 33（4），1689- 1706。弗朗西斯，D.P.，Raimond，K.，2017年。核主元分析近似方法在分类任务中的实证评估arXiv预印本arXiv：1712.04196。弗朗西斯，D.P.，Raimond，K.，2018年a. 参数化频繁方向算法的一种改进。数据最小知识发现32（2），453-482。弗朗西斯，D.P.，Raimond，K.，2018年b月。一种基于随机傅立叶特征的大数据集异常检测流算法。在：大数据和云计算的进展。施普林格，pp. 209-217Ghashami，M.，德赛，A.，菲利普斯，J.M.，2014.改进的实用矩阵素描与保证。欧洲算法研讨会（European Symposium on Algorithms）施普林格，pp. 467- 479Ghashami，M.，佩里，DJ，Phillips，J.，2016.流式内核主成分分析。在：人工智能和统计。pp. 公元1365-1374年。Golub，G.H.，扎，H.，1995.矩阵对的典型相关及其数值计算。在：线性代数信号处理。施普林格，pp. 27-49.古普塔湾Agrawal，D.P.，山口，S.，2016.计算机与网络安全现代密码解决方案IGIGlobal.黄，H. ，Kasiviswanathan ，S.P. ，2015.使用随机矩阵草