上海交通大学学报（英文版） ›› 2012, Vol. 17 ›› Issue (2): 141-146.doi: 10.1007/s12204-012-1243-7

• 论文 • 上一篇    下一篇

A Relaxed-PPA Contraction Method for Sparse Signal Recovery

FU Xiao-ling 1* (符小玲), WANG Xiang-feng 2 (王祥丰)   

  1. (1. Institute of Systems Engineering, School of Economics and Management, Southeast University, Nanjing 210096, China; 2. Department of Mathematics, Nanjing University, Nanjing 210093, China)
  • 出版日期:2012-04-28 发布日期:2012-05-31
  • 通讯作者: FU Xiao-ling 1* (符小玲), E-mail:fuxlnju@hotmail.com

A Relaxed-PPA Contraction Method for Sparse Signal Recovery

FU Xiao-ling 1* (符小玲), WANG Xiang-feng 2 (王祥丰)   

  1. (1. Institute of Systems Engineering, School of Economics and Management, Southeast University, Nanjing 210096, China; 2. Department of Mathematics, Nanjing University, Nanjing 210093, China)
  • Online:2012-04-28 Published:2012-05-31
  • Contact: FU Xiao-ling 1* (符小玲), E-mail:fuxlnju@hotmail.com

摘要： Sparse signal recovery is a topic of considerable interest, and the literature in this field is already quite immense. Many problems that arise in sparse signal recovery can be generalized as a convex programming with linear conic constraints. In this paper, we present a new proximal point algorithm (PPA) termed as relaxed-PPA (RPPA) contraction method, for solving this common convex programming. More precisely, we first reformulate the convex programming into an equivalent variational inequality (VI), and then efficiently explore its inner structure. In each step, our method relaxes the VI-subproblem to a tractable one, which can be solved much more efficiently than the original VI. Under mild conditions, the convergence of the proposed method is proved. Experiments with l1 analysis show that RPPA is a computationally efficient algorithm and compares favorably with the recently proposed state-of-the-art algorithms.

关键词: sparse signal recovery, proximal point algorithm (PPA), convex programming, contraction method

Abstract: Sparse signal recovery is a topic of considerable interest, and the literature in this field is already quite immense. Many problems that arise in sparse signal recovery can be generalized as a convex programming with linear conic constraints. In this paper, we present a new proximal point algorithm (PPA) termed as relaxed-PPA (RPPA) contraction method, for solving this common convex programming. More precisely, we first reformulate the convex programming into an equivalent variational inequality (VI), and then efficiently explore its inner structure. In each step, our method relaxes the VI-subproblem to a tractable one, which can be solved much more efficiently than the original VI. Under mild conditions, the convergence of the proposed method is proved. Experiments with l1 analysis show that RPPA is a computationally efficient algorithm and compares favorably with the recently proposed state-of-the-art algorithms.

Key words: sparse signal recovery, proximal point algorithm (PPA), convex programming, contraction method

中图分类号: