在线咨询
中国工业与应用数学学会会刊
主管:中华人民共和国教育部
主办:西安交通大学
ISSN 1005-3085  CN 61-1269/O1

工程数学学报 ›› 2025, Vol. 42 ›› Issue (1): 59-76.

• • 上一篇    下一篇

基追踪去噪问题的新型投影算法

薛 兵1,  郑作奎2   

  1. 1. 临沂大学数学与统计学院,临沂 276005
    2. 山东省费县第二中学,费县 273400
  • 收稿日期:2022-06-02 接受日期:2023-04-06 出版日期:2025-02-15 发布日期:2025-04-15
  • 基金资助:
    国家自然科学基金(12071250; 11801309);山东省自然科学基金(ZR2021MA088).

New Type Projection Algorithm for Basis Pursuit Denoising Problem

XUE Bing1,  ZHENG Zuokui2   

  1. 1. School of Mathematics and Statistics, Linyi University, Linyi 276005
    2. No.2 Middle School of Feixian, Shandong Province, Feixian 273400
  • Received:2022-06-02 Accepted:2023-04-06 Online:2025-02-15 Published:2025-04-15
  • Supported by:
    The National Natural Science Foundation of China (12071250; 11801309);the Natural Science Foundation of Shandong Province (ZR2021MA088).

摘要:

基追踪去噪(Basis Pursuit Den-Noising, BPDN)问题是稀疏信号恢复问题的一个重要模型。求解BPDN问题的数值算法已经得到了广泛的研究,但当该问题的维数增加较大时,一些求解算法的速度和精度仍有待提高。因此,构建求解BPDN问题速度快、精度高的优化算法是重要且具有挑战性的问题。基于BPDN问题中的决策变量分解为两个非负变量,将其等价的转化为线性互补问题,构建了每次迭代只需计算一次函数值和在非负象限上进行一次投影的特殊迭代格式的新型投影算法,其中新算法每次迭代不需要进行任何线搜索寻找步长,也不需要计算绝对值函数次微分。同时,对新设计算法产生序列的全局收敛性进行了详细证明。对不同情况下BPDN问题的数值实验,验证了新构建算法的有效性。因此,所设计的新算法提升了求解高维数BPDN问题的效率和精度,具有一定的理论价值和实际意义。

关键词: 基追踪去噪, 稀疏信号重构, 算法, 全局收敛

Abstract:

Basis pursuit de-noising (BPDN) problem is considered to be an important model encountered in the sparse signal reconstruction problem. A lot of numerical algorithms about solving the BPDN problems have been extensively developed, but the solving speed and accuracy are still need improved when the dimension increases greatly. Therefore, it is an important and challenging problem to construct an optimization algorithm with faster solution speed and higher accuracy for solving BPDN problems. Based on splitting the decision variable into two nonnegative auxiliary variables in the BPDN problems, and transform BPDN problems into linear complementarity problems. Based on a special iterative format, we present a new projection algorithm without any line search to find a suitable step size and computation of the subdifferential of the absolute value function, which needs only one value of the mapping per iteration and only one projection onto the nonnegative quadrant. At the same time, the global convergence of iterative sequences generated by the new algorithm is established in detail. Numerical experiments on the BPDN problems with different cases are also given to verify the effectiveness of the proposed method. Thus, the proposed new method improves the efficiency and accuracy of solving the high dimensional the BPDN problems, and have certain theoretical value and practical significance.

Key words: basis pursuit denoising, sparse signal reconstruction, algorithm, global convergence

中图分类号: