Abstract
Frequently, the most important information in a signal is much sparser than the signal itself. In this paper, we study a projected conjugate gradient method for finding sparse solutions to an undetermined linear system arising from compressive sensing. The construction of this method consists of two main phases: (1) reformulate a l 1 regularized least squares problem into an equivalent nonlinear system of monotone equations; (2) apply a conjugate gradient method with projection strategy to the resulting system. The derived method only needs matrix-vector products at each step and could be easily implemented. Global convergence result is established under some suitable conditions. Numerical results demonstrate that the proposed method can improve the computation time while obtaining similar reconstructed quality.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Mean Square Error
- Conjugate Gradient Method
- Compressive Sense
- Quadratic Programming Problem
- Sparse Signal
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Chen, S., Donoho, D.L., Saunders, M.: Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing 20, 33–61 (1998)
Daubechies, I., Fornasier, M., Loris, I.: Accelerated projection gradient method for linear inverse problems with sparsity constraints. Journal of Fourier Analysis and Applications 14, 764–792 (2008)
Duarte, M.F., Eldar, Y.C.: Structured compressed sensing: from theory to applications. IEEE Transactions on Signal Processing 59, 4053–4085 (2011)
Grippo, L., Sciandrone, M.: Nonmonotone derivative-free methods for nonlinear equations. Computational Optimization and Applications 37, 297–328 (2007)
Figueiredo, M.A.T., Nowak, R.D., Wright, S.J.: Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. IEEE Journal of Selected Topics in Signal Processing 1, 586–598 (2007)
Pang, J.S.: Inexact Newton methods for the nonlinear complementary problem. Mathematical Programming 36, 54–71 (1986)
Solodov, M.V., Svaiter, B.F.: A globally convergent inexact Newton method for systems of monotone equations. In: Fukushima, M., Qi, L. (eds.) Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smooth Methods, pp. 355–369. Kluwer Academic Publishers (1998)
Xiao, Y.H., Wang, Q.Y., Hu, Q.J.: Non-smooth equations based method for l 1 −norm problems with applications to compressed sensing. Nonlinear Analysis: Theory, Methods & Applications 74, 3570–3577 (2011)
Yan, Q.R., Peng, X.Z., Li, D.H.: A globally convergent derivative-free method for solving large-scale nonlinear monotone equations. Journal of Computational and Applied Mathematics 234, 649–657 (2010)
Yu, G.H., Niu, S.Z.: Multivariate spectral gradient projection method for large-scale nonlinear systems of monotone equations, http://www.paper.edu.cn/index.php/default/en_releasepaper/downPaper/201201-778
Zhang, L., Zhou, W.J., Li, D.H.: A descent modified Polak-Ribiere-Polyak conjugate gradient method and its global convergence. IMA Journal of Numerical Analysis 26, 629–640 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Qiu, Y., Xue, W., Yu, G. (2013). A Projected Conjugate Gradient Method for Compressive Sensing. In: Yang, J., Fang, F., Sun, C. (eds) Intelligent Science and Intelligent Data Engineering. IScIDE 2012. Lecture Notes in Computer Science, vol 7751. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36669-7_49
Download citation
DOI: https://doi.org/10.1007/978-3-642-36669-7_49
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36668-0
Online ISBN: 978-3-642-36669-7
eBook Packages: Computer ScienceComputer Science (R0)