A Splitting-based Iterative Method for Sparse Reconstruction
Abstract
In this paper, we study a ℓ1-norm regularized minimization method for sparse solution recovery in compressed sensing and X-ray CT image reconstruction. In the proposed method, an alternating minimization algorithm is employed to solve the involved ℓ1-norm regularized minimization problem. Under some suitable conditions, the proposed algorithm is shown to be globally convergent. Numerical results indicate that the presented method is effective and promising.References
J. Barzilai and J. Borwein, Two point step size gradient methods, IMA J Numer. Anal., vol. 8, pp. 141-148, 1988.
E. G. Birgin, J. M. Martinez and M. Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., vol.10, pp. 1196-1121, 2000.
S. Becker, J. Bobin and E. Candes, NESTA: A fast and accurate first-order method for sparse recovery, SIAM J. Imag. Sci., vol. 4, pp. 1-39, 2011.
A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imag. Sci., vol. 2,no. 1, pp. 183-202, 2009.
A. Chambolle, An algorithm for total variation minimization and applications, Journal of Mathematical imaging and vision, vol. 20, pp. 89-97, 2004.
L. Combettes and R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., vol. 4, pp. 1168-1200, 2005.
J. Cai, S. Osher and Z. Shen, Linearized Bregman iterations for compressive sensing, Mathematics of Computation, vol. 78, no. 267,pp. 1515-1536, 2009.
J. Cai, S. Osher and Z. Shen, Convergence of the linearized Bregman iteration for ℓ1-norm minimization, Mathematics of Computation, vol. 78, no. 268, pp. 2127-2136, 2009.
L. Donoho, De-noising by soft-thresholding, Information Theory, IEEE Transactions on, vol. 41, no. 3, pp. 613-627, 1995..
I. Daubechies, M. Defriese and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,Commun. Pure Appl. Math., vol. LVII, pp. 1413-1457, 2004.
M. Elad, Why simple shrinkage is still relevant for redundant representations? IEEE Trans. Inform. Theory, vol. 52, no.12, pp. 5559-5569, 2006.
M. Figueiredo, R. Nowak and S. J. Wright, Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Signa., vol. 1, pp. 586-597, 2007.
M. Figueiredo and R. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Imag. Process., vol. 12, no. 8, pp. 906-916, 2003.
B.S. He, M. Tao and X.M. Yuan, A splitting method for separable convex programming, IMA Journal of Numerical Analysis, vol. 35, no. 1, pp. 394-426, 2015.
Y. Huang, K. Ng and W.Wen, A fast total variation minimization method for image restoration, SIAM Multiscale Model. Simul. vol. 7, no. 2, pp. 774-795, 2008.
E. Hale, W. Yin and Y. Zhang, Fixed-point continuation for ℓ1-minimization: methodology and convergence, SIAM J. Optim., vol. 19, no. 3, pp. 1107-1130, 2008.
E. Hale, W. Yin and Y. Zhang, Fixed-point continuation applied to compressed sensing: implementation and numerical experiments, J Comput. Math., vol. 28, no. 2, pp. 170-194, 2010.
R. Nowak and M. Figueiredo, Fast wavelet-based image deconvolution using the EM algorithm, in Proceedings of the 35th Asilomar Conference on Signals, Systems and Computers, vol. 1, pp. 371-375, 2001.
Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Amer. Math. Soc., vol. 73, pp. 591-597, 1967.
Z. Shen, Z. Geng and J. Yang, Image reconstruction from incomplete convolution data via total variation regularization, Stat., Optim. Inf. Comput., Vol. 3, pp. 1-14, 2015.
J. Starck, E. Candes and D. Donoho, Astronomical image representation by the curvelet transform, Astron. Astrophys., vol. 398, pp. 785-800, 2003.
J.-L. Starck, M. Nguyen and F. Murtagh, Wavelets and curvelets for image deconvolution: a combined approach, Signal Process., vol. 83, pp. 2279-2283, 2003.
W. Wang and Q. Wang, Approximated Function Based Spectral Gradient Algorithm for Sparse Signal Recovery, Stat., Optim. Inf. Comput., Vol. 2, pp 10-20, 2014.
S. Wright, R. Nowak and M. Figueiredo, Sparse reconstruction by separable approximation, in Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, October 2008.
W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for ℓ1-minimization with applications to compressed sensing, SIAM J. Imag. Sci., vol. 1, no. 1, pp. 143-168, 2008.
W. Yin, The linearized Bregman method: reviews, analysis, and generalizations, CAAM TR09C02, Rice University.
M. Friedlander and E. Van den Berg, Probing the pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., vol. 31, no. 2, pp. 890-912, 2008.
J. Yang and Y. Zhang, Alternating direction algorithms for ℓ1-problem in compressive sensing, SIAM J. Sci. Comput., vol. 33, pp. 250-278, 2011.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
