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.
FU Xiao-ling 1* (符小玲), WANG Xiang-feng 2 (王祥丰)
. A Relaxed-PPA Contraction Method for Sparse Signal Recovery[J]. Journal of Shanghai Jiaotong University(Science), 2012
, 17(2)
: 141
-146
.
DOI: 10.1007/s12204-012-1243-7
[1] Chent S S, Donoho D, Saunders M A. Atomic decomposition by basis pursuit [J]. SIAM Journal on Scientific Computing, 1998, 20(1): 33-61.
[2] Donoho D L. Compressed sensing [J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.
[3] Bunea F, Tsybakov A, Wegkamp M. Sparsity oracle inequalities for the Lasso [J]. Electronic Journal of Statistics, 2007, 1: 169-194.
[4] Wainwright M J. Sharp thresholds high-dimensional and for noisy sparsity recovery using l1-constrained quadratic programming (Lasso) [J]. IEEE Transactions
on Information Theory, 2009, 55(5): 2183-2202.
[5] Wright S J, Nowak R D, Figueiredo M A T. Sparse reconstruction by separable approximation [J]. IEEE Transactions on Signal Processing, 2009, 57(7):2479-2493.
[6] Cand`es E J, Tao T. The Dantzig selector: Statistical estimation when p is much larger than n [J]. Annals of Statistics, 2007, 35(6): 2313-2351.
[7] Romberg J. The Dantzig selector and generalized thresholding [C]//42nd Annual Conference on Information Sciences and Systems. Princeton, USA: IEEE,2008: 22-25.
[8] Wang X, Yuan X. The linearized alternating direction methods for dantzig selector [R]. Nanjing, China:Nanjing University, 2011.
[9] Becker S, Bobin J, Cand`es E J. NESTA: A fast and accurate first-order method for sparse recovery [J].SIAM Journal on Imaging Sciences, 2011, 4(1): 1-39.
[10] Becker S, Cand`es E J, Grant M. Templates for convex cone problems with applications to sparse signal recovery [J]. Mathematical Programming Computation,
2011, 3(3): 165-218.
[11] Cand`es E J, Plan Y. Near-ideal model selection by l1 minimization [J]. The Annals of Statistics, 2009,37(5A): 2145-2177.
[12] Beck A, Teboulle M. A fast iterative shrinkagethresholding algorithm for linear inverse problems [J].SIAM Journal on Imaging Sciences, 2009, 2(1): 183-
202.
[13] Combettes P L, Wajs V R. Signal recovery by proximal forward-backward splitting [J]. Multiscale Modeling and Simulation, 2005, 4(4): 1168-1200.
[14] Nesterov Y. Gradient methods for minimizing composite objective function [R]. Louvain-la-Neuve, BE:Catholic University of Louvain, 2007.
[15] Rockafellar R T. Monotone operators and the proximal point algorithm [J]. Journal on Control and Optimization, 1976, 14(5): 877-898.
