关于Kaczmarz的一类加速免伪逆贪婪块方法.pdf
《关于Kaczmarz的一类加速免伪逆贪婪块方法.pdf》由会员分享,可在线阅读,更多相关《关于Kaczmarz的一类加速免伪逆贪婪块方法.pdf(19页珍藏版)》请在咨信网上搜索。
1、Advances in Applied Mathematics 应用数学进展应用数学进展,2024,13(1),466-484 Published Online January 2024 in Hans.https:/www.hanspub.org/journal/aam https:/doi.org/10.12677/aam.2024.131046 文章引用文章引用:颜鑫鹏,时文雅,郇战.关于 Kaczmarz 的一类加速免伪逆贪婪块方法J.应用数学进展,2024,13(1):466-484.DOI:10.12677/aam.2024.131046 关于关于Kaczmarz的一类加速免伪逆贪
2、婪块方法的一类加速免伪逆贪婪块方法 颜鑫鹏,时文雅,郇颜鑫鹏,时文雅,郇 战战*常州大学阿里云大数据学院,江苏 常州 收稿日期:2023年12月27日;录用日期:2024年1月21日;发布日期:2024年1月30日 摘摘 要要 块贪婪块贪婪Kaczmarz方法在解决大规模一致线性系统方面取得了成功应用。然而在每次迭代步骤中,方法在解决大规模一致线性系统方面取得了成功应用。然而在每次迭代步骤中,GBK方法都涉及伪逆计算,这不仅复杂化了计算并减慢了收敛速度,且不适合分布式实现。在本文中基于方法都涉及伪逆计算,这不仅复杂化了计算并减慢了收敛速度,且不适合分布式实现。在本文中基于Sketching技术
3、提出了两种免伪逆计算的技术提出了两种免伪逆计算的GBK方法,分别是杠杆得分抽样免伪逆方法,分别是杠杆得分抽样免伪逆GBK方法和稀疏随机投影方法和稀疏随机投影免伪逆免伪逆GBK方法,其算法效率更加方法,其算法效率更加高效高效,收敛速度可以达到指数收敛。为了进一步加快收敛速度,我们,收敛速度可以达到指数收敛。为了进一步加快收敛速度,我们还提出了还提出了CountSketch免伪逆重力球免伪逆重力球GBK方法、杠杆得分抽样免伪逆重力球方法、杠杆得分抽样免伪逆重力球GBK方法和稀疏随机投影免方法和稀疏随机投影免伪逆重力球伪逆重力球GBK方法。为了验证新方法的有效性,我们进行了一些数值示例。结果表明,这
4、些新方法在方法。为了验证新方法的有效性,我们进行了一些数值示例。结果表明,这些新方法在解决大规模一致线性系统方面具有很解决大规模一致线性系统方面具有很高的效率和准确性。高的效率和准确性。关键词关键词 贪婪块贪婪块Kaczmarz方法,收敛性,大规模相容线性方程组,方法,收敛性,大规模相容线性方程组,矩阵矩阵Sketching技术,免伪逆计算技术,免伪逆计算 Accelerated Pseudo-Inverse-Free Greedy Block Methods in the Kaczmarz Algorithm Category Xinpeng Yan,Wenya Shi,Zhan Huan*
5、Aliyun School of Big Data,Changzhou University,Changzhou Jiangsu Received:Dec.27th,2023;accepted:Jan.21st,2024;published:Jan.30th,2024 Abstract The Greedy Block Kaczmarz(GBK)method has been successfully applied in solving large-scale consistent linear systems.However,each iteration of the GBK method
6、 involves the computation of *通讯作者。颜鑫鹏 等 DOI:10.12677/aam.2024.131046 467 应用数学进展 pseudoinverses,which complicates the process,slows down convergence,and is ill-suited for dis-tributed implementations.In this paper,we introduce two free pseudoinverse GBK methods based on Sketching techniques:the Leve
7、rage Score Sampling Free Pseudoinverse GBK method and the Sparse Random Projection Free Pseudoinverse GBK method.These algorithms exhibit higher effi-ciency and can achieve exponential rates of convergence.To further accelerate convergence,we also propose the Count Sketch Free Pseudoinverse Heavy Ba
8、ll GBK method,the Leverage Score Sampling Free Pseudoinverse Heavy Ball GBK method,and the Sparse Random Projection Free Pseudoinverse Heavy Ball GBK method.The effectiveness of these new methods is demonstrated through several numerical examples,showing that they are highly efficient and accurate i
9、n ad-dressing large-scale consistent linear systems.Keywords Greedy Block Kaczmarz Method,Convergence,Large-Scale Compatible Linear Equation Systems,Matrix Sketching Techniques,Pseudo-Inverse Calculation Copyright 2024 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Comm
10、ons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 大规模相容线性方程组的高效求解对科学与工程应用1 2 3 4 5具有重要意义和实际价值。,m nmAxb Ab=(1)经典 Kaczmarz 算法6以其结构简明和易于实施的特点,在大规模线性方程组求解中显现优势。该算法每次迭代仅处理单个行样本,保证了简洁高效,尽管其收敛性难以与其他迭代方法7 8进行比较且可能较慢。研究人员正致力于优化 Kaczmarz 算法,以提升其在实际应用中的表现,确保在科学和工
11、程领域的高效解决方案。Strohmer 和 Vershynin 9近期提出的随机 Kaczmarz(RK)方法,以其依赖于矩阵规范化条件数的快速收敛性而备受关注。该方法采用概率策略选取矩阵行指标,即根据公式()222kiFAPrA=来选择行指标,能在特定条件下超越传统共轭梯度法。研究者对 Kaczmarz 方法持续优化,扩展至包括不相容、欠定和秩亏线性方程组10 11 12的收敛性分析,并引入 Nesterov 加速框架13 14和贪婪策略15 16 17 18等加速技巧。这些进展对解决线性方程组和优化问题领域产生了深远影响。块 Kaczmarz(BK)方法19及其变体如随机块 Kaczmar
12、z(RBK)20、随机双块 Kaczmarz(RDBK)21和贪婪块 Kaczmarz(GBK)22,针对线性方程组求解展现出高效迭代性能。这些算法通过分块策略,有效利用方程信息,实现快速收敛。特别是在处理不相容系统和大规模数据时,这些方法通过随机选择和贪婪选择块,优化了迭代过程,提升了稳定性和收敛性。块高斯 Kaczmarz 方法(BGK)23融合高斯Sketching 技术,优化分布式计算性能,实现大型线性系统的有效分解与并行解算。然而,算法中伪逆计算和最小二乘问题求解的高计算量是挑战所在,优化这些关键步骤是当前研究的焦点。Necoara 提出的随机平均块 Kaczmarz(RABK)方法
13、24,Moorman 等25研究了 RABK 方法在解不相Open AccessOpen Access颜鑫鹏 等 DOI:10.12677/aam.2024.131046 468 应用数学进展 容线性方程组中的收敛性理论,其衍生的简单随机扩展平均块 Kaczmarz(REABK)方法26,该方法结合了随机扩展 Kaczmarz(REK)方法27和 RABK 方法。Du 和 Sun 扩展了该方法,并提出了一种免于使用伪逆的随机块迭代算法28,适用于解决一致与不一致线性方程组。最近,Zhang Jianhua 等人在 REABK 的基础上推出了快速免伪逆贪婪块 Kaczmarz(CFGBK)方法2
14、9,在处理相容与不相容线性方程组方面展现出高效性,但是随着研究发现该方法由于每步迭代()22iA存在出现为零的情况导致收敛失败,本文提出了一种新型加速免伪逆贪婪对该问题进行了研究并解决。矩阵 Sketching 技术作为提升矩阵运算速度的关键工具,在偏微分方程反问题30、优化31与回归分析32 33 34 35等多个领域发挥着至关重要的作用。本研究创新性地提出了两种基于近似最大距离准则的免伪逆贪婪块 Kaczmarz 方法(LFGBK、CFGBK),通过精心选择采样矩阵和迭代策略,显著缩短了运算时间,同时保持了精度,并深入分析了其收敛性。此外,借助重力球技术,进一步提出了三种加速方法(CMFG
15、BK、LMFGBK、CMFGBK),并建立了完备的收敛性理论框架。经过数值实验验证,这些方法不仅提高了计算效率,也为矩阵 Sketching 技术的进一步优化奠定了坚实基础。本文结构如下:第二节介绍预备知识和贪婪块 Kaczmarz 方法和免伪逆贪婪块 Kaczmarz 方法。第三节提出改进免伪逆贪婪块 Kaczmarz 方法并给分析。第四节给出数值实验。第五节总结全文。2.预备知识预备知识 在本文中,我们采用文献中17同样的记号。例如()iA、TA、A、A、FA、n分别表示系数矩阵 A 的第 i 行、转置、广义逆、谱范数、F-范数和集合1,2,n?。我们首先考虑贪婪选择规则,然后使用贪婪策略
16、提供一个贪婪块 Kaczmarz 算法。在研究贪婪选择规则在 kaczmarz 型算法中的应用的文献中,很少有结果。Nutini 等人在16中提出了 Kaczmarz 算法的最大残差(MR)和最大距离(MD)规则。然而,在许多应用程序中,由于其复杂的表达式,计算精确的 MR 或MD 规则将过于低效,但我们可以通过使用更便宜的近似贪婪规则来近似它,如18方法。在本节中,我们将考虑计算贪婪规则直至乘法误差的方法。再给出收敛性分析之前首先介绍引理。引理引理 1 36让 0ttF是一个非负实数矩阵,其中01FF=满足关系式1121tttFa Fa F+对所有1t 成立,这里20a 且121aa+。对所
17、有1t 下列不等式成立:()101ttFqF+其中,211114,2aaaqqa+=和12qaa+。引理引理 2 17如果任意向量()Turange A,则()22T22minAuA A u 引理引理 3 35 37如果 S 是含有()22O n行稀疏随机变换,其中那么不等式()()22211,nAxSAxAxx+和()()()()()11,1,0,1,iiiSAASAid +成立的概率均为1。定义定义 1 35(CountSketch 变换):设 :hmd是一个随机映射,使得每个 im,()h ij=对每个 jd成立的概率为 1/d,0,1d m是一个dm二值矩阵,其中其余元素均为 0。D
18、是mm。随机对颜鑫鹏 等 DOI:10.12677/aam.2024.131046 469 应用数学进展 角矩阵,每个对角元素以相同的概率独立选择值为 1 或者1。则 CountSketch 变换定义为d mSD=。定义 1 描述了 CountSketch 变换的基本过程:首先,通过随机映射 h 和二值矩阵将输入矩阵的行映射到较低的维度空间;然后,通过随机对角矩阵 D 对映射后的结果进行随机翻转。这个过程可以有效地减小矩阵的大小,同时保持某些重要的信息。Algorithm 1.基于流形式的 CountSketch 方法 1:输入:m nA 2:将初始化为dn全零矩阵 3:for 1,km=?4
19、:从集合 d中随机均匀地选择样本值 l 5:从集合1,1中随机均匀地选择样本值 g 6:使用:llkccga+更新 C 的第 l 行 7:end for 8:返回d nC 定义定义 2 38 39(Leverage Score Sampling 变换):给定矩阵m nA,其奇异值分解为TAUDV=,其 行杠杆得分给出 U 行的欧几里得范数得平方,即对于每个 jd,22T22jjjUe Uu=?,同时满足01j?和njijp=?。杠杆得分抽样也可以描述为“帽矩阵”。定义 2 描述了 Leverage Score Sampling 变换的基本过程,首先设 A 是一个nd的矩阵,每一行的Levera
20、ge Score 是该行在 A 的奇异值分解中对应的右奇异向量的范数的平方。这个得分衡量了每一行在数据集中的重要性或影响力。这种采样方法的优点是,它可以从大数据集中选择出一小部分具有代表性的样本,从而进行更高效的计算。所得到的样本集k dSR,其中 k 是选定的样本数量,可以用于估计原矩阵 CA 的各种性质,例如奇异值分解、主成分分析等。Algorithm 2.基于流形式的 Leverage Score Sampling 方法 1:输入:m nA 2:将初始化为dn全零矩阵 3:设置变量0sum=4:计算 A 的奇异值分解,U S V 5:for 1,km=?6:对 U 的每一行求平方和,加入
21、到 sum 7:计算每个数据点被抽样的概率:U 的每一行求平方和,除以 sum 8:根据计算出的概率进行抽样,得到抽样索引 indices 9:使用,:Cindices=10:end for 11:返回d nC 定义定义 3 40(Sparse Random Projection 变换):设矩阵m nA,其中()0,1ijAN,则()01ijP Am=。定义 3 描述了 Sparse Random Projection 变换的基本过程,首先 Sparse Random Projection 投影后的维度 k,然后构造一个dk的稀疏矩阵 R。对于 R 中的每一列,我们随机选择一个元素并赋值为+1
22、 或1,其余元素设为 0。这个稀疏随机矩阵的每一列都只有一个非零元素,该元素的位置在每一列中都是随机选择的,其值是根据一个预先定义的分布随机选择的。这种方法的优点是它的计算效率高,因为乘以稀颜鑫鹏 等 DOI:10.12677/aam.2024.131046 470 应用数学进展 疏矩阵的计算复杂度低。这种方法在处理高维数据时,特别是在近似最近邻搜索和其他需要降维的应用中,被广泛使用。此外,由于 R 的元素大部分是 0,所以投影后的数据也会保持原始数据的稀疏性。Algorithm 3.基于流形式的 Sparse Random Projection 方法 1:输入:m nA 2:将 C 初始化为
23、dn全零矩阵 3:生成dm稀疏随机矩阵 S,其中非零元素的概率为1m 4:使CS=5:返回d nC 定义定义 4 36(Heavy Ball Momentum 优化):重球动量是一种广泛添加到梯度下降方法中的增强方法,它在每个迭代步骤中不仅采取梯度下降的步骤,还额外在前一迭代步骤的移动方向上采取一步。这一方法最初由 Polyak 在 1964 年提出,后来在机器学习领域广泛应用。Algorithm 4.Heavy Ball Momentum 优化方法 1:将初始化,0v=2:Set 10 xx=3:while ture 4:()()()()T1122kikikkkittiiibA xxxwAx
24、xA+=+5:end while 6:返回 x 假设我们已经近似了 MD 规则,其中有一个参数(0,1,用于选择指标ki()()()()2222122maxikiikikki miikbAxbA xAA Niu 和 Zheng 将贪婪策略与块 Kaczmarz 方法相结合,提出了求解大型相容线性方程组的贪婪块Kaczmarz(GBK)22方法,具体过程见算法 5。Algorithm 5.GBK 方法 1:输入:()T0,A b l xrange A和参数()0,1 2:输出:lx 3:for 0,1,1kl=?do 4:计算()()2212maxii xkki mibAA=5:确定指标集序列(
25、)()2202:kkikkkkiikkkibAxAx=6:计算()1kkkkkkxxAbA x+=+7:end for 颜鑫鹏 等 DOI:10.12677/aam.2024.131046 471 应用数学进展 GBK 方法的收敛性分析描述如下:定理定理 1 22设线性方程组(1)相容,则由算法 7 生成的迭代序列收敛到方程组的最小范数解*xA b=,且对任意0k 满足()()12221*20*221kminkkFAxxxxA+其中()()122222kkkFFkmaxFFAAAAA=(记()()00202FmaxAA),(0,1,()minA和()maxA分别表示矩阵 A 的非零最小奇异值和
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关于 Kaczmarz 一类 加速 免伪逆 贪婪 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。