2025年4月4日 周五
首页本刊简介投稿须知编委会成员论文撰写模板论文格式要求过刊全文链接审稿单联系我们English
首页 > 过刊浏览>2021年第49卷第11期 >1505-1513. DOI:10.11908/j.issn.0253-374x.21212
PDF HTML阅读 XML下载 导出引用 引用提醒
求解线性方程组稀疏解的稀疏贪婪随机Kaczmarz算法
CSTR:
[cstr]
作者:
作者单位:

同济大学 数学科学学院，上海 200092

作者简介:

王 泽（1998—），男，博士生，主要研究方向为数值代数与科学计算。 E-mail： math_wangze@tongji.edu.cn

通讯作者:

殷俊锋（1979—），男，教授，博士生导师，理学博士，主要研究方向为数值代数与科学计算。 E-mail： yinjf@tongji.edu.cn

中图分类号:

O241.6

基金项目:

国家自然科学基金（11971354）


Sparse Greedy Randomized Kaczmarz Method for Sparse Solutions to Linear Equations
Author:
Affiliation:

School of Mathematical Sciences， Tongji University， Shanghai 200092， China

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [22]
    • |
  • 相似文献 [3]
    • | | |
  • 文章评论
    摘要:

    求解线性方程组的稀疏解在图像重构、信号处理和机器学习等领域中具有广泛的应用，通过引入l1-范数正则化，可以转化为求解一个约束优化问题。基于一种选择系数矩阵工作行的概率准则，提出了稀疏贪婪随机Kaczmarz算法，并给出了有噪声干扰和无噪声干扰情况下该算法的收敛性分析。理论表明本文算法的收缩因子小于随机稀疏Kaczmarz算法的收缩因子。数值实验验证了本文算法的有效性。

    Abstract:

    The sparse solution to linear equations has been widely used in image reconstruction， signal processing， and machine learning. By introducing l1 norm regularization， it can be transformed into solving a constrained optimization problem. Based on a novel probability criterion for selecting the working rows from the coefficient matrix， a sparse greedy randomized Kaczmarz method was proposed， and the convergence analysis of the novel method with and without noise interference were conducted， which showed that the convergence factor of the novel method was smaller than that of the randomized sparse Kaczmarz method. The numerical experiments verified the effectiveness of the proposed method.

    参考文献
    [1] TSAIG Y， DONOHO D L. Extensions of compressed sensing [J]. Signal Processing， 2005， 86（3）：549.
    [2] CANDES E， ROMBERG J， TAO T. Stable signal recovery from incomplete and inaccurate measurements [J]. Communications on Pure and Applied Mathematics， 2006， 59（8）：1207.
    [3] ELAD M. Sparse and redundant representations： From theory to applications in signal and image processing [M]. Berlin： Springer， 2010.
    [4] BYRD R H， CHIN G M， WU Y， et al. Sample size selection in optimization models for machine learning [J]. Mathmatical Programming， 2012， 134（1）：127.
    [5] CHEN S S， DONOHO D L， SAUNDERS M A. Atomic decomposition by basis pursuit [J]. SIAM Review， 2001， 43（1）： 129.
    [6] YIN W， OSHER S， GOLDFARB D， et al. Bregman iterative algorithms for l1-minimization with applications to compressed sensing [J]. SIAM Journal on Imaging Sciences， 2008， 1（1）： 143.
    [7] SCHO?PFER F. Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions [J]. SIAM Journal on Optimization， 2016， 26（3）： 1883.
    [8] STROHMER T， VERSHYNIN R. A randomized Kaczmarz algorithm with exponential convergence [J]. Journal of Fourier Analysis and Applications， 2009， 15（2）： 262.
    [9] NEEDELL D， TROPP J A. Paved with good intensions： Analysis of a randomized block Kaczmarz method [J]. Linear Algebra and its Applications， 2014， 441（1）： 199.
    [10] AGASKAR A， WANG C， LU Y M. Randomized Kaczmarz algorithms： Exact MSE analysis and optimal sampling probabilities [C]// 2014 IEEE Global Conference on Signal and Information Processing （Global SIP）. [s.l.]： IEEE， 2015： 389-393.
    [11] LIU J， WRIGHT S. An accelerated randomized Kaczmarz algorithm [J]. Mathematics of Computation， 2016， 85（297）： 153.
    [12] LORENZ D A， SCHO?PFER F， WENGER S. A sparse Kaczmarz solver and a linearized Bregman method for online compressed sensing [C]//2014 IEEE International Conference on Image Processing （ICIP）. [s.l.]：IEEE，2015：1347-1351.
    [13] LORENZ D A， SCHO?PFER F， WENGER S. The linearized Bregman method via split feasibility problems： Analysis and generalizations [J]. SIAM Journal on Imaging Sciences， 2014， 7（2）：1237.
    [14] ZOUZIAS A， FRERIS N M. Randomized extended Kaczmarz for solving least squares[J]. SIAM Journal on Matrix Analysis and Applications， 2013， 34（2）： 773.
    [15] NEEDELL D. Randomized Kaczmarz solver for noisy linear system [J]. BIT Numerical Mathematics， 2010， 50（2）： 395.
    [16] SCHO?PFER F， LORENZ D A. Linear convergence of the randomized sparse Kaczmarz method [J]. Mathematical Programming， 2019， 173（1/2）： 509.
    [17] 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： A592.
    [18] 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.
    [19] 杜亦疏， 殷俊锋， 张科. 求解大型稀疏线性方程组的贪婪距离随机Kaczmarz算法[J]. 同济大学学报（自然科学版），2020，48（8）： 1224. DOI： 10.11908/j. issn. 0253-374x. 20041.
    [20] 荆燕飞，李彩霞，胡少亮. 求解大型稀疏线性系统的贪婪双子空间随机Kaczmarz方法 [J]. 同济大学学报（自然科学版），2021， 49（10）： 1473. DOI： 10.11908/j. issn. 0253-374x. 21054.
    [21] MANSOUR H， YILMAZ O. A fast randomized Kaczmarz algorithm for sparse solutions of consistent linear system [J]. arXiv， 2013， 1305.3803v1.
    [22] ROCKAFELLAR R T， WETS R， et al. Variational analysis [M]. Berlin： Springer，2009.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

王泽,殷俊锋.求解线性方程组稀疏解的稀疏贪婪随机Kaczmarz算法[J].同济大学学报(自然科学版),2021,49(11):1505~1513

复制
分享
文章指标
  • 点击次数:580
  • 下载次数: 1329
  • HTML阅读次数: 191
  • 引用次数: 0
历史
  • 收稿日期:2021-05-12
  • 在线发布日期: 2021-11-29
文章二维码

您是本站第 10436042 访问者

版权所有：《同济大学学报（自然科学版）》     主管单位：教育部    主办单位：同济大学

地址：上海市四平路1239号同济大学内    邮编：200092    电话：021-65982344     E-mail：zrxb@tongji.edu.cn

本系统由北京勤云科技发展有限公司设计