zbMATH — the first resource for mathematics

Incomplete variables truncated conjugate gradient method for signal reconstruction in compressed sensing. (English) Zbl 1355.94018
Summary: Compressed sensing (CS) has stirred great interests in many fields of science, due to its ability to capture most information of compressible signals at a rate significantly below the Nyquist rate. Reconstructing the signal from random measurements is an important topic in CS. In this paper, a new algorithm – Incomplete variables Truncated Conjugate Gradient method (ITCG) is proposed to reconstruct the signal by solving a programming with \(\ell_1\) norm. By adjusting the parameters of ITCG, two specific algorithms are presented, i.e. ITCG-vs for very sparse reconstruction and ITCG-nvs for not very sparse reconstruction. To make full use of the sparse nature of signals, ITCG can reconstruct them efficiently. The experiments show that the two algorithms of ITCG (especially ITCG-nvs) are much faster than competing methods in sparse reconstruction. In addition, it has been shown that ITCG-vs can converge after finite iterations under some decent conditions.

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
Full Text: DOI
[1] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 183-202, (2009) · Zbl 1175.94009
[2] Bioucas-Dias, J.; Figueiredo, M., A new twist: two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Trans. Image Process., 16, 2992-3004, (2007)
[3] E. Candès, Compressive sampling, in: Proceedings of the International Congress of Mathematicians, Madrid, Spain, 2006, pp. 1433-1452.
[4] Candès, E.; Tao, T., Decoding by linear programming, IEEE Trans. Inform. Theory, 51, 4203-4215, (2005) · Zbl 1264.94121
[5] Chen, S.; Donoho, D.; Saunders, M., Atomic decomposition by basis pursuit, SIAM Rev., 43, 129-159, (2001) · Zbl 0979.94010
[6] Cheng, B.; Yang, J.; Yan, S.; Huang, T., Learning with L1 graph for image analysis, IEEE Trans. Image Process., 19, 858-866, (2010) · Zbl 1371.68229
[7] W. Dai, O. Milenkovic, Subspace Pursuit for Compressive Sensing Signal Reconstruction, arXiv:0803.0811v3 [cs.NA] 8 January 2009. · Zbl 1367.94082
[8] Daubechies, I.; Defrise, M.; DeMol, C., An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57, 1413-1457, (2004) · Zbl 1077.65055
[9] Daubechies, I.; Fornasier, M.; Loris, I., Accelerated projected gradient method for linear inverse problems with sparsity constraints, J. Fourier Anal. Appl., 14, 764-792, (2008) · Zbl 1175.65062
[10] Davis, G.; Mallat, S.; Avellaneda, M., Adaptive greedy approximations, J. Construct. Approx., 13, 57-98, (1997) · Zbl 0885.41006
[11] Donoho, D., Compressed sensing, IEEE Trans. Inform. Theory, 52, 1289-1306, (2006) · Zbl 1288.94016
[12] Donoho, D.; Tsaig, Y.; Drori, I.; Starck, J., Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit, IEEE Trans. Inform. Theory, 58, 1094-1121, (2012) · Zbl 1365.94069
[13] Efron, B.; Hastie, T.; Johnstone, I.; Tibshirani, R., Least angle regression, Ann. Statist., 32, 407-499, (2004) · Zbl 1091.62054
[14] Fan, R.; Chen, P.; Lin, C., Working set selection using second order information for training support vector machines, J. Mach. Learn. Res., 6, 1889-1918, (2005) · Zbl 1222.68198
[15] Figueiredo, M.; Bioucas-Dias, J.; Nowak, R., Majorization-minimization algorithms for wavelet-based image restoration, IEEE Trans. Image Process., 16, 2980-2991, (2007)
[16] Figueiredo, M.; Nowak, R., An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process., 12, 906-916, (2003) · Zbl 1279.94015
[17] Figueiredo, M.; Nowak, R.; Wright, S., Gradient projection for sparse application to compressed sensing and other inverse problems, IEEE J. Select. Topics Signal Process., 1, 586-597, (2007)
[18] Hale, E.; Yin, W.; Zhang, Y., Fixed-point continuation for \(\ell_1\)-minimization: methodology and convergence, SIAM J. Optim., 19, 1107-1130, (2008) · Zbl 1180.65076
[19] Kim, S.; Koh, K.; Lustig, M.; Boyd, S.; Gorinvesky, D., A interior-point method for large-scale \(\ell_1\)-regularized least squares, IEEE J. Select. Topics Signal Process., 1, 606-617, (2007)
[20] Lyons, M.; Budynek, J.; Akamatsu, S., Automatic classification of single facial images, IEEE Trans. Pattern Anal. Mach. Intell., 21, 1357-1362, (1999)
[21] Mallat, S.; Zhang, Z., Matching pursuits with time-frequency dictionaries, IEEE Trans. Signal Process., 41, 3397-3415, (1993) · Zbl 0842.94004
[22] P. Nagesh, B. Li, A compressive sensing approach for expression-invariant face recognition, in: Proc. IEEE Int. Conf. Comput. Vis. Pattern Recognit., 2009, pp. 1518-1525.
[23] Needell, D.; Tropp, J., Cosamp: iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmonic Anal., 26, 301-321, (2009) · Zbl 1163.94003
[24] Needell, D.; Vershynin, R., Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, Found. Comput. Math., 9, 317-334, (2009) · Zbl 1183.68739
[25] Y. Nesterov, Gradient Methods for Minimizing Composite Objective Function, CORE report, 2007. <http://www.ecore.be/DPs/dp_1191313936.pdf>.
[26] E. Osuna, R. Freund, F. Girosi, An improved algorithm for support vector machines, in: Proc. IEEE Signal Processing Society Workshop (NNSP’97), Amelia Island, USA, 1997, pp. 276-285.
[27] Qi, H.; Qi, L.; Sun, D., Soving karush-Kuhn-Tucker systems via trust region and the conjugate gradient methods, SIAM J. Optim., 14, 439-463, (2003) · Zbl 1052.65060
[28] Starck, J.; Candès, E.; Donoho, D., Astronomical image representation by the curvelet transform, Astron. Astrophys., 398, 785-800, (2003)
[29] Starck, J.; Nguyen, M.; Murtagh, F., Wavelets and curvelets for image deconvolution: a combined approach, Signal Process., 83, 2279-2283, (2003) · Zbl 1145.94329
[30] Tsaig, Y.; Donoho, D., Extensions of compressed sensing, Signal Process., 86, 549-571, (2006) · Zbl 1163.94399
[31] Tseng, P.; Yun, S., A coordinate gradient descent method for nonsmooth separable minimization, Math. Prog., 117, 387-423, (2009) · Zbl 1166.90016
[32] Wright, J.; Yang, A.; Ganesh, A.; Sastry, S.; Ma, Y., Robust face recognition via sparse representation, IEEE Trans. Pattern Anal. Mach. Intell., 31, 210-227, (2009)
[33] S. Yan, H. Wang, Semi-supervised learning by sparse representation, in: Proceedings of SIAM International Conference on Data Mining (SDM), 2009, pp. 792-801.
[34] J. Yang, K. Yu, Y. Gong, T. Huang, Linear spatial pyramid matching using sparse coding for image classification, in: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2009, pp. 1794-1801.
[35] J. Yang, Y. Zhang, Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing, (preprint) arXiv:0912.1185, 2009. · Zbl 1256.65060
[36] Yun, S.; Toh, K., A coordinate gradient descent method for \(\ell_1\)-regularized convex minimization, Comput. Optim. Appl., 48, 273-307, (2011) · Zbl 1220.90092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.