Two-step version of fixed point continuation method for sparse reconstruction

Abstract

l₁-regularized problems have a wide application in various areas such as signal processing. It minimizes a quadratic function combined with an l₁ 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

l₁ regularized problem / iterative soft-thresholding / fixed point continuation / sparse reconstruction / signal processing / image deconvolution / compressed sensing

References

[1] Barzilai J., Borwein J. Two point step size gradient methods. IMA Journal of Numerical Analysis, 1988, 8: 141-148.

[2] Bioucas-Dias J., Figueiredo M. A new TwIST: Two-Step Iterative Shrinkage/Thresholding algorithms for image restoration. IEEE Transactions on Image Processing, 2007, 16: 2992-3004.

[3] Figueiredo M., Nowak R. An EM algorithm for wavelet-based image restoration. IEEE Transactions on Image Processing, 2003, 12: 906-916.

[4] Figueiredo M, Nowak R. A bound optimization approach to wavelet-based image deconvolution. IEEE International Conference on Image Processing—ICIP’ 2005, 2005

[5] Figueiredo M., Nowak R., Wright S. J. Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. IEEE Journal of Selected Topics in Signal Processing, 2007, 1: 586-597.

[6] Hale E. T., Yin W., Zhang Y. Fixed-point continuation for ℓ₁-minimization: Methodology and convergence. SIAM Journal on Optimization, 2008, 19(3): 1107-1130.

[7] Kim S., Koh K., Lustig M., Boyd S., Gorinversky D. An interior-point method for large-scale l₁ regularized least squares. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 606-617.

[8] Lu L., Pearce C. Some new bounds for singular values and eigenvalues of matrix products. Annals of Operations Research, 2000, 98: 141-148.

[9] Nowak R, Figueiredo M. Fast wavelet-based image deconvolution using the EM algorithm. In: Proceedings of the 35th Asilomar Conference on Signals, Systems, and Computers, Monterey, CA, 2001

[10] Rockafellar R. T. Monotone operators and the proximal point algorithm. SIAM J Control and Optimization, 1976, 14(5): 877-898.

[11] Tibshirani R. Regression shrinkage and selection via the lasso. Journal Royal Statistical Society B, 1996, 58: 267-288.

[12] Zeidler E. Nonlinear Functional Analysis and Its Applications II/B: Nonlinear Monotone Operators, 1990, Berlin: Springer.