Large sparse signal recovery by conjugate gradient algorithm based on smoothing technique. (English) Zbl 1391.94481
Summary: Finding sparse solutions to under-determined linear systems of equations have intensively involved in fields of machine learning, signal processing, compressive sensing, linear inverse problems and statistical inference. Generally, the task can be realized by solving \(\ell_1\)-norm regularized minimization problems. However, the resulting problem is challenging due to the non-smoothness of the regularization term. Inspired by Nesterov’s smoothing technique, this paper proposes, analyzes and tests a modified Polak-Ribière-Polyak conjugate gradient method to solve large-scale \(\ell_1\)-norm least squares problem for sparse signal recovery. The per-iteration cost of the proposed algorithm is dominated by three matrix-vector multiplications and the global convergence is guaranteed by results in optimization literature. Moreover, the algorithm is also accelerated by continuation loops as usual. The limited experiments show that this continuation technique benefits to its performance. Numerical experiments which decode a sparse signal from its limited measurements illustrate that the proposed algorithm performs better than NESTA – a recently developed code with Nesterov’s smoothing technique and gradient algorithm.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 94A13 | Detection theory in information and communication theory |
| 65F22 | Ill-posedness and regularization problems in numerical linear algebra |
| 65K10 | Numerical optimization and variational techniques |
Keywords:
compressive sensing; non-smooth optimization; conjugate gradient method; sparse solution; \(\ell_1\)-norm regularizationReferences:
| [1] | Shen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decompositon by basis pursuit, SIAM J. Sci. Comput., 20, 33-61 (1998) · Zbl 0919.94002 |
| [2] | Shen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decompositon by basis pursuit, SIAM Rev., 43, 129-159 (2001) · Zbl 0979.94010 |
| [3] | Donoho, D. L., For most large underdetemind systems of linear equations, the minimal \(\ell_1\)-norm solution is also the sparsest solution, Comm. Pure Appl. Math., 59, 907-934 (2006) · Zbl 1105.90068 |
| [4] | Tibshirani, R., Regression shrinkage and selection via the Lasso, J. Roy. Statist. Soc., 58, 267-268 (1996) · Zbl 0850.62538 |
| [5] | Friedlander, M.; Van den Berg, E., Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 890-912 (2008) · Zbl 1193.49033 |
| [6] | Candès, E.; Romberg, J.; Tao, T., Stable signal recovery from incomplete and inaccurate information, Comm. Pure Appl. Math., 59, 1207-1233 (2005) · Zbl 1098.94009 |
| [7] | Candès, E.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52, 489-509 (2006) · Zbl 1231.94017 |
| [8] | Donoho, D. L., Compressed sensing, IEEE Trans. Inform. Theory, 52, 1289-1306 (2006) · Zbl 1288.94016 |
| [9] | De Mol, C.; Defrise, M., A note on wavelet-based inversion algorithms, Contemp. Math., 313, 85-96 (2002) · Zbl 1039.47010 |
| [10] | Figueiredo, M. A.T.; Nowak, R. D., An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process., 12, 906-916 (2003) · Zbl 1279.94015 |
| [11] | Daubechies, I.; Defrise, M.; De Mol, C., An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57, 1413-1457 (2004) · Zbl 1077.65055 |
| [12] | Elad, M., Why simple shrinkage is still relevant for redundant representations?, IEEE Trans. Inform. Theory, 52, 5559-5569 (2006) · Zbl 1309.94035 |
| [13] | Starck, J. L.; Nguyen, M.; Murtagh, F., Wavelets and curvelets for image deconvolution: a combined approach, Signal Process., 83, 2279-2283 (2003) · Zbl 1145.94329 |
| [14] | Hale, E. T.; Yin, W.; Zhang, Y., Fixed-point continuation for \(\ell_1\)-minimization: methodology and convergence, SIAM J. Optim., 19, 1107-1130 (2008) · Zbl 1180.65076 |
| [15] | Hale, E. T.; Yin, W.; Zhang, Y., Fixed-point continuation applied to compressed sensing: implementation and numerical experiments, J. Comput. Math., 28, 170-194 (2010) · Zbl 1224.65153 |
| [16] | Barzilai, J.; Borwein, J. M., Two point step size gradient method, IMA J. Numer. Anal., 8, 141-148 (1988) · Zbl 0638.65055 |
| [17] | Bioucas-Dias, J. M.; Figueiredo, M. A.T., A new TwIST: two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Trans. Image Process., 16, 2992-3004 (2007) |
| [18] | 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 |
| [20] | Broughton, R. L.; Coope, I. D.; Renaud, P. F.; Tappenden, R. E.H., A box constrained gradient projection algorithm for compressed sensing, Signal Process., 91, 1985-1992 (2011) · Zbl 1217.94036 |
| [21] | Figueiredo, M. A.T.; Nowak, R. D.; Wright, S. J., Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Signal Process., 586-597 (2007), IEEE Press, Piscataway, NJ |
| [22] | Yun, S.; Toh, K. C., A coordinate gradient descent method for \(\ell_1\)-regularized convex minimization, Comput. Optim. Appl., 48, 273-307 (2011) · Zbl 1220.90092 |
| [23] | Berg, E.; Friedlander, M. P., Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 890-912 (2008) · Zbl 1193.49033 |
| [24] | Birgin, E. G.; Martínez, J. M.; Raydan, M., Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., 10, 1196-1211 (2000) · Zbl 1047.90077 |
| [25] | Becker, S.; Bobin, J.; Candès, E., NESTA: a fast and accurate first-order method for sparse recovery, SIAM J. Imaging Sci., 4, 1-39 (2011) · Zbl 1209.90265 |
| [27] | Yang, J.; Zhang, Y., Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing, SIAM J. Sci. Comput., 33, 250-278 (2011) · Zbl 1256.65060 |
| [28] | Xiao, Y.; Zhu, H.; Wu, S.-Y., Primal and dual alternating direction algorithms for \(\ell_1 - \ell_1\)-norm minimization problems in compressive sensing, Comput. Optim. Appl., 54, 441-459 (2013) · Zbl 1269.90081 |
| [29] | Zhang, L.; Zhou, W.; Li, D., A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence, IMA J. Numer. Anal., 26, 629-640 (2006) · Zbl 1106.65056 |
| [30] | Nesterov, Y., Smooth minimization of non-smooth functions, Math. Program., 103, 127-152 (2005) · Zbl 1079.90102 |
| [31] | Chen, X.; Zhou, W., Smoothing nonlinear conjugate gradient method for image restoration using nonsmooth nonconvex minimization, SIAM J. Imaging Sci., 3, 765-790 (2010) · Zbl 1200.65031 |
| [32] | Zhang, J.; Xiao, Y.; Wei, Z., Nonlinear conjugate gradient methods with sufficient descent condition for large-scale unconstrained optimization, Math. Probl. Eng., 2009 (2009), ID: 243290 · Zbl 1184.65066 |
| [33] | Black, M. J.; Rangarajan, A., On the unification of line processes, outlier rejection and robust statistics with applications in early vision, Int. J. Comput. Vis., 19, 57-91 (1996) |
| [34] | Osborne, M. R.; Presnell, B.; Turlach, B. A., A new approach to variable selection in least squares problems, IMA J. Numer. Anal., 20, 389-403 (2000) · Zbl 0962.65036 |
| [35] | Donoho, D. L.; Tsaig, Y., Fast solution of \(\ell_1\) minimization problems when the solution may be sparse, IEEE Trans. Inform. Theory, 54, 4789-4812 (2008) · Zbl 1247.94009 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
