|
|
Two-step version of fixed point continuation
method for sparse reconstruction |
Hao WANG1,Hongying LIU2,Yong XIA2, |
1.Key Laboratory of
Ministry of Education for Information Mathematics and Behavior, School
of Mathematics and Systems Science, Beijing University of Aeronautics
and Astronautics, Beijing 100191, China;Department of Industrial
and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USA; 2.Key Laboratory of
Ministry of Education for Information Mathematics and Behavior, School
of Mathematics and Systems Science, Beijing University of Aeronautics
and Astronautics, Beijing 100191, China; |
|
|
Abstract l1-regularized problems have a wide application in various areas such as signal processing. It minimizes a quadratic function combined with an l1 norm term. Iterative soft-thresholding method (IST) is originally proposed to deal with these problems, and fixed point continuation algorithm (FPC) was proposed recently as an improved version of IST. This paper obtains a two-step version of FPC (TwFPC) by combining the new iterate of FPC with its previous two iterates. We also provide an analysis for the convergence of FPC and TwFPC. Various numerical experiments on image deconvolution and compressed sensing show that TwFPC improves IST significantly and is much faster than other competing codes. What is more important, it is very robust to the involved parameters and the regularization parameter.
|
Keywords
l1-regularized problem
iterative soft-thresholding
fixed point continuation
sparse reconstruction
signal processing
image deconvolution
compressed sensing
|
Issue Date: 05 September 2010
|
|
|
Barzilai J, Borwein J. Two point step size gradientmethods. IMA Journal of Numerical Analysis, 1988, 8: 141―148
doi: 10.1093/imanum/8.1.141
|
|
Bioucas-Dias J, Figueiredo M. A new TwIST: Two-Step IterativeShrinkage/Thresholding algorithms for image restoration. IEEE Transactions on Image Processing, 2007, 16: 2992―3004
doi: 10.1109/TIP.2007.909319
|
|
Figueiredo M, Nowak R. An EM algorithm for wavelet-basedimage restoration. IEEE Transactions onImage Processing, 2003, 12: 906―916
doi: 10.1109/TIP.2003.814255
|
|
Figueiredo M, Nowak R. A bound optimization approachto wavelet-based image deconvolution. IEEEInternational Conference on Image Processing—ICIP’ 2005, 2005
|
|
Figueiredo M, Nowak R, Wright S J. Gradient projection for sparse reconstruction: Applicationto compressed sensing and other inverse problems. IEEE Journal of Selected Topics in Signal Processing, 2007, 1: 586―597
doi: 10.1109/JSTSP.2007.910281
|
|
Hale E T, Yin W, Zhang Y. Fixed-point continuation for ?1-minimization:Methodology and convergence. SIAM Journalon Optimization, 2008, 19(3): 1107―1130
doi: 10.1137/070698920
|
|
Kim S, Koh K, Lustig M, Boyd S, Gorinversky D. An interior-point methodfor large-scale l1-regularized least squares. IEEE Journalof Selected Topics in Signal Processing, 2007, 1(4): 606―617
doi: 10.1109/JSTSP.2007.910971
|
|
Lu L, Pearce C. Some new bounds for singularvalues and eigenvalues of matrix products. Annals of Operations Research, 2000, 98: 141―148
doi: 10.1023/A:1019200322441
|
|
Nowak R, Figueiredo M. Fast wavelet-based imagedeconvolution using the EM algorithm. In: Proceedings of the 35th Asilomar Conference on Signals, Systems,and Computers, Monterey, CA, 2001
|
|
Rockafellar R T. Monotone operators and the proximal point algorithm. SIAM J Control and Optimization, 1976, 14(5): 877―898
doi: 10.1137/0314056
|
|
Tibshirani R. Regressionshrinkage and selection via the lasso. Journal Royal Statistical Society B, 1996, 58: 267―288
|
|
Zeidler E. NonlinearFunctional Analysis and Its Applications II/B: Nonlinear MonotoneOperators. Berlin: Springer, 1990
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|