ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals. (English) Zbl 1284.65055

This article develops an algorithm for underdetermined least squares problems with 1-norm constraint on the solution. It relies on a modified Nestorev method that periodically updates the prox-center optimally and renders the proposed method almost always linearly convergent. The method is then applied to find the minimum 1-norm solution to an underdetermined least squares problem when teamed with the Pareto root finder. Numerical tests show that these methods achieve comparable numerical results in comparable time for such a problem in image processing and other areas of application.


65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F50 Computational methods for sparse matrices
65K05 Numerical mathematical programming methods
90C25 Convex programming
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
Full Text: DOI arXiv


[1] Afonso, M., Bioucas-Dias, J., Figueiredo, M.: Fast image recovery using variable splitting and constrained optimization. IEEE Trans. Image Process. 19(9), 2345-2356 (2010) · Zbl 1371.94018
[2] Afonso, M., Bioucas-Dias, J., Figueiredo, M.: Fast frame-based image deconvolution using variable splitting and constrained optimization. In: IEEE/SP 15th Workshop on Statistical Signal Processing, 2009. SSP ’09, pp. 109-112 (2009)
[3] Barzilai, J., Borwein, J.: Two point step size gradient method. IMA J. Numer. Anal. 8(1), 141-148 (1988) · Zbl 0638.65055
[4] Beck, A., Teboulle, M.: Fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2(1), 183-202 (2009) · Zbl 1175.94009
[5] Becker, S., Bobin, J., Candès, E. J.: nesta: a fast and accurate first-order method for sparse recovery. SIAM J. Imag. Sci. 4(1), 1-39 (2011) · Zbl 1209.90265
[6] Bertsekas, D.P.: Nonlinear Programming. Belmont, MA (1999) · Zbl 1203.90153
[7] Birgin, E., Martínez, J., Raydan, M.: Nonmonotone spectral projected-gradient methods on convex sets. SIAM J. Optim. 10(4), 1196-1211 (2000) · Zbl 1047.90077
[8] Bobin, J., Stark, J.-L., Ottensamer, R.: Compressed sensing in astronomy. IEEE J. Sel. Top. Signal Process. 2(5), 718-726 (2008)
[9] Candès, E.J.: The restricted isometry property and its implications for compressed sensing. C. R. Math. Acad. Sci. Paris 346(9-10), 589-592 (2008) · Zbl 1153.94002
[10] Candès, E.J., Tao, T.: The Dantzig selector: statistical estimation when p is much larger than n. Ann. Stat. 35(6), 2313-2351 (2007) · Zbl 1139.62019
[11] Candès, E.J., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207-1223 (2006) · Zbl 1098.94009
[12] Chen, S., Donoho, D.L., Saunders, M.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33-61 (1998) · Zbl 0919.94002
[13] Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact newton methods. SIAM J. Numer. Anal. 19(2), 400-408 (1982) · Zbl 0478.65030
[14] Donoho, D.L.: For most large underdetermined systems of linear equations the ℓ1-norm solution is also the sparsest solution. Commun. Pure Appl. Math. 59(6), 797-829 (2006) · Zbl 1113.15004
[15] Duchi, J., Shalev-Shwartz, S., Singer, Y., Chandra, T.: Efficient projections onto the ℓ1-ball for learning. Proc. Int. Conf. Mach. Learn. (ICML ’08) 25(307), 272-279 (2008)
[16] Efron, B., Hastie, T., Johnstone, I., Tibshirani, R.: Least angle regression. Ann. Stat. 32(2), 407-499 (2004) · Zbl 1091.62054
[17] Figueiredo, M., Nowak, R., Wright, S.: Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal Process. 1(4), 586-597 (2007)
[18] Figueiredo, M., Nowak, R., Wright, S.: Sparse reconstruction by separable approximation. IEEE Trans. Signal Process. 577, 2479-2493 (2009) · Zbl 1391.94442
[19] Friedman, J., Hastie, T., Höfling, H., Tibshirani, R.: Pathwise coordinate optimization. Ann. Appl. Stat. 1(2), 302-332 (2007) · Zbl 1378.90064
[20] Fuchs, J.J.: On sparse representations in arbitrary redundant bases. IEEE Trans. Inf. Theory 50(6), 1344 (2004) · Zbl 1284.94018
[21] Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979) · Zbl 0411.68039
[22] Hale, E.T., Yin, W., Zhang, Y.: A fixed-point continuation method for ℓ1-regularized minimization with applications to compressed sensing. Rice University Technical Report (2007) · Zbl 1180.65076
[23] Hale, E.T., Yin, W., Zhang, Y.: Fixed-point continuation for ℓ1-minimization: methodology and convergence. SIAM J. Optim. 19(3), 1107-1130 (2008) · Zbl 1180.65076
[24] Hennenfent, G., Herrmann, F.J.: Sparseness-constrained data continuation with frames: applications to missing traces and aliased signals in 2/3-D. SEG Tech. Program Expanded Abstracts 24(1), 2162-2165 (2005)
[25] Hennenfent, G., Herrmann, F.J.: Simply denoise: wavefield reconstruction via jittered undersampling. Geophysics 73(3), V19-V28 (2008)
[26] Natarajan, B.K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 24(2), 227-234 (1995) · Zbl 0827.68054
[27] Nesterov, Y.: A method for solving the convex programming problem with convergence rate O(1/k2). Dokl. Akad. Nauk SSSR 269(3), 543-547 (1983)
[28] Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103(1), 127-152 (2005) · Zbl 1079.90102
[29] Nesterov, Y.: Gradient methods for minimizing composite objective function. CORE Discussion Paper 2007/76 (2007) · Zbl 1091.62054
[30] Osborne, M.R., Presnell, B., Turlach, B.A.: On the lasso and its dual. J. Comput. Graph. Stat. 9(2), 319-337 (2000)
[31] Osborne, M.R., Presnell, B., Turlach, B.A.: A new approach to variable selection in least squares problems. IMA J. Numer. Anal. 20(3), 389-403 (2000) · Zbl 0962.65036
[32] Ponomarev, S.P.: Submersions and preimages of sets of measure zero. Sib. Math. J. 28(1), 153-163 (1987) · Zbl 0623.28002
[33] Romberg, J.: Imaging via compressive sensing. IEEE Trans. Signal Process. 25(2), 14-20 (2008)
[34] Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc., Ser. B Stat. Methodol. 58(1), 267-288 (1996) · Zbl 0850.62538
[35] Tropp, J.A.: Just relax: convex programming methods for identifying sparse signals in noise. IEEE Trans. Inf. Theory 52(3), 1030-1051 (2006) · Zbl 1288.94025
[36] Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization. Preprint (2008) · Zbl 1209.90265
[37] van den Berg, E., Friedlander, M.P.: Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31(2), 890-912 (2008/09) · Zbl 1193.49033
[38] van den Berg, E., Friedlander, M.P., Hennenfent, G., Herrmann, F.J., Saab, R., Yilmaz, Ö.: Algorithm 890: sparco: a testing framework for sparse reconstruction. ACM Trans. Math. Softw. 35(4), 16 (2009)
[39] Wen, Z., Yin, W., Goldfarb, D., Zhang, Y.: A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization and continuation. SIAM J. Sci. Comput. 32(4), 1832 (2010) · Zbl 1215.49039
[40] Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for l1 minimization with applications to compressed sensing. SIAM J. Imag. Sci. 1(1), 143-168 (2008) · Zbl 1203.90153
[41] Yu, Y.L.: Nesterov’s optimal gradient method. LLL, Jul. 30 2009 (2009). http://webdocs.cs.ualberta.ca/ yaoliang/Non-smooth
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.