求解大型线性最小二乘问题的贪婪Gauss-Seidel方法

doi:10.11908/j.issn.0253-374x.21201

首页 > 过刊浏览>2021年第49卷第11期 >1514-1521. DOI:10.11908/j.issn.0253-374x.21201

求解大型线性最小二乘问题的贪婪Gauss-Seidel方法
DOI:
                        10.11908/j.issn.0253-374x.21201
                    
CSTR:
                        [cstr]
                    
作者:
                        李寒宇李寒宇
重庆大学 数学与统计学院， 重庆 401331
在期刊界中查找
在百度中查找
在本站中查找
张彦钧张彦钧
重庆大学 数学与统计学院， 重庆 401331
在期刊界中查找
在百度中查找
在本站中查找

                    
作者单位:重庆大学 数学与统计学院， 重庆 401331
作者简介:李寒宇（1981—）， 男， 教授， 博士生导师， 理学博士， 主要研究方向为随机数值代数与张量计算。 E-mail： hyli@cqu.edu.cn
通讯作者:
中图分类号:O241.6
基金项目:国家自然科学基金（11671060）；重庆市自然科学基金（cstc2019jcyj-msxmX0267）

A Greedy Gauss-Seidel Method for Solving the Large Linear Least Squares Problem

Author:

LI Hanyu
LI Hanyu
College of Mathematics and Statistics， Chongqing University， Chongqing 401331， China
在期刊界中查找
在百度中查找
在本站中查找
ZHANG Yanjun
ZHANG Yanjun
College of Mathematics and Statistics， Chongqing University， Chongqing 401331， China
在期刊界中查找
在百度中查找
在本站中查找

Affiliation:

College of Mathematics and Statistics， Chongqing University， Chongqing 401331， China

Fund Project:

摘要

图/表

访问统计

参考文献 [35]

相似文献 [3]

引证文献

资源附件

文章评论

摘要:

基于一种选择系数矩阵A的工作列的策略，提出了求解大型线性最小二乘问题的一种不同的贪婪Gauss-Seidel方法，并对该方法进行了收敛性分析。数值实验表明，在相同的精度下，所提方法在计算时间上优于文献提出的贪婪随机坐标下降方法。

关键词:贪婪Gauss-Seidel方法;贪婪随机坐标下降方法;随机的Gauss-Seidel方法;大型线性最小二乘问题

Abstract:

An alternative greedy Gauss-Seidel method for solving the large linear least squares problem is proposed based on a novel strategy for choosing the working columns of the coefficient matrix A， and the convergence of the new method is analyzed. The numerical experiments show that for the same accuracy， the method proposed in this paper outperforms the greedy randomized coordinate descent method proposed recently in term of the computing time.

Key words:greedy Gauss-Seidel method;greedy randomized coordinate descent method;randomized Gauss-Seidel method;large linear least squares problem

参考文献

[1] BJ?RCK ?. Numerical methods for least squares problems [M]. Philadelphia：Society for Industrial and Applied Mathematics， 1996.

[2] HIGHAM N J. Accuracy and stability of numerical algorithms [M]. Philadelphia：Society for industrial and applied mathematics， 2002.

[3] SAAD Y. Iterative methods for sparse linear systems [M]. Philadelphia：Society for Industrial and Applied Mathematics， 2003.

[4] HEFNY A， Needell D， Ramdas A. Rows versus columns： Randomized Kaczmarz or Gauss-Seidel for ridge regression [J]. SIAM Journal on Scientific Computing， 2017， 39（5）： S528.

[5] STROHMER T， VERSHYNIN R. A randomized Kaczmarz algorithm with exponential convergence [J]. Journal of Fourier Analysis and Applications， 2009， 15（2）： 262.

[6] LEVENTHAL D， LEWIS A S. Randomized methods for linear constraints： Convergence rates and conditioning [J]. Mathematics of Operations Research， 2010， 35（3）： 641.

[7] MA A， NEEDELL D， RAMDAS A. Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods [J]. SIAM Journal on Matrix Analysis and Applications， 2015， 36（4）： 1590.

[8] EDALATPOUR V， HEZARI D， SALKUYEH D K. A generalization of the Gauss-Seidel iteration method for solving absolute value equations [J]. Applied Mathematics and Computation， 2017， 293： 156.

[9] TU S， VENKATARAMAN S， WILSON A C， et al. Breaking locality accelerates block Gauss-Seidel [C]//International Conference on Machine Learning. Sydney： PMLR， 2017： 3482-3491.

[10] CHEN L， SUN D， TOH K C. An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming [J]. Mathematical Programming， 2017， 161（1/2）： 237.

[11] TIAN Z， TIAN M， LIU Z， et al. The Jacobi and Gauss–Seidel-type iteration methods for the matrix equation AXB= C [J]. Applied Mathematics and Computation， 2017， 292： 63.

[12] XU Y. Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming [J]. SIAM Journal on Optimization， 2018， 28（1）： 646.

[13] DU K. Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss-Seidel algorithms [J]. Numerical Linear Algebra with Applications， 2019， 26（3）： e2233.

[14] RAZAVIYAYN M， HONG M， REYHANIAN N， et al. A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems [J]. Mathematical Programming， 2019， 176（1/2）： 465.

[15] BAI Z Z， WU W T. On greedy randomized coordinate descent methods for solving large linear least-squares problems [J]. Numerical Linear Algebra with Applications， 2019， 26（4）： e2237.

[16] BAI Z Z， WU W T. On greedy randomized Kaczmarz method for solving large sparse linear systems [J]. SIAM Journal on Scientific Computing， 2018， 40（1）： A592.

[17] BAI Z Z， WU W T. On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems [J]. Applied Mathematics Letters， 2018， 83： 21.

[18] 杜亦疏，殷俊锋，张科.求解大型稀疏线性方程组的贪婪距离随机Kaczmarz方法[J].同济大学学报（自然科学版），2020，48（8）：1224.

[19] NUTINI J. Greed is good： Greedy optimization methods for large-scale structured problems [D]. Vancouver ： University of British Columbia， 2018.

[20] ZHANG J J. A new greedy Kaczmarz algorithm for the solution of very large linear systems [J]. Applied Mathematics Letters， 2019， 91： 207.

[21] DU K， GAO H. A new theoretical estimate for the convergence rate of the maximal weighted residual Kaczmarz algorithm [J]. Numerical Mathematics： Theory， Methods and Applications， 2019， 12（2）： 627.

[22] LIU Y， GU C Q. Variant of greedy randomized Kaczmarz for ridge regression [J]. Applied Numerical Mathematics， 2019， 143： 223.

[23] NIU Y Q， ZHENG B. A greedy block Kaczmarz algorithm for solving large-scale linear systems [J]. Applied Mathematics Letters， 2020， 104： 106294.

[24] ZHANG J， GUO J. On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems [J]. Applied Numerical Mathematics， 2020， 157： 372.

[25] OSBORNE E E. On least squares solution of linar equations [J]. Journal of the Association for Computing Machinery， 1961， 8： 628.

[26] HADDOCK J， NEEDELL D. On Motzkin’s method for inconsistent linear systems [J]. BIT Numerical Mathematics， 2019， 59（2）： 387.

[27] REBROVA E， NEEDELL D. Sketching for Motzkin’s iterative method for linear systems [C]//53rd Asilomar Conference on Signals， Systems， and Computers. Pacific Grove： IEEE， 2019： 271-275.

[28] MOTZKIN T S， SCHOENBERG I J. The relaxation method for linear inequalities [J]. Canadian Journal of Mathematics， 1954， 6： 393.

[29] NUTINI J， SEPEHRY B， LARADJI I， et al. Convergence rates for greedy Kaczmarz algorithms， and faster randomized Kaczmarz rules using the orthogonality graph [J]. arXiv preprint arXiv，2016：1612.07838.

[30] PETRA S， POPA C. Single projection Kaczmarz extended algorithms [J]. Numerical Algorithms， 2016， 73（3）： 791.

[31] DU K， SI W， SUN X. Randomized extended average block Kaczmarz for solving least squares [J]. SIAM Journal on Scientific Computing， 2020， 42（6）： A3541.

[32] DU K， SUN X. A doubly stochastic block Gauss-Seidel algorithm for solving linear equations [J]. Applied Mathematics and Computation， 2021， 408： 126373.

[33] NECOARA I. Faster randomized block Kaczmarz algorithms [J]. SIAM Journal on Matrix Analysis and Applications， 2019， 40（4）： 1425.

[34] LI H， ZHANG Y. Greedy block Gauss-Seidel methods for solving large linear least squares problem [J]. arXiv preprint arXiv， 2020： 2004.02476.

[35] DAVIS T A， HU Y. The University of Florida sparse matrix collection [J]. ACM Transactions on Mathematical Software （TOMS）， 2011， 38（1）： 1.

引用本文

李寒宇,张彦钧.求解大型线性最小二乘问题的贪婪Gauss-Seidel方法[J].同济大学学报(自然科学版),2021,49(11):1514~1521

复制

文章指标

点击次数:242
下载次数: 887
HTML阅读次数: 225
引用次数: 0

历史

收稿日期:2021-05-10
最后修改日期:
录用日期:
在线发布日期: 2021-11-29
出版日期:

引用本文

分享

文章指标

历史

文章二维码

引用本文

分享

微信扫一扫：分享

文章指标

历史

文章二维码