×

The matrix splitting based proximal fixed-point algorithms for quadratically constrained \(\ell_{1}\) minimization and Dantzig selector. (English) Zbl 1379.65039

Appl. Numer. Math. 125, 23-50 (2018); corrigendum ibid. 126, 199 (2018).
Summary: This paper studies algorithms for solving quadratically constrained \(\ell_1\) minimization and Dantzig selector which have recently been widely used to tackle sparse recovery problems in compressive sensing. The two optimization models can be reformulated via two indicator functions as special cases of a general convex composite model which minimizes the sum of two convex functions with one composed with a matrix operator. The general model can be transformed into a fixed-point problem for a nonlinear operator which is composed of a proximity operator and an expansive matrix operator, and then a new iterative scheme based on the expansive matrix splitting is proposed to find fixed-points of the nonlinear operator. We also give some mild conditions to guarantee that the iterative sequence generated by the scheme converges to a fixed-point of the nonlinear operator. Further, two specific proximal fixed-point algorithms based on the scheme are developed and then applied to quadratically constrained \(\ell_1\) minimization and Dantzig selector. Numerical results have demonstrated that the proposed algorithms are comparable to the state-of-the-art algorithms for recovering sparse signals with different sizes and dynamic ranges in terms of both accuracy and speed. In addition, we also extend the proposed algorithms to solve two harder constrained total-variation minimization problems.

MSC:

65K05 Numerical mathematical programming methods
90C25 Convex programming

Software:

NESTA; PDCO; SPGL1; TFOCS; Yall1
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bauschke, H. H.; Combettes, P. L., Convex Analysis and Monotone Operator Theory in Hilbert Spaces (2011), Springer Science & Business Media · Zbl 1218.47001
[2] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202 (2009) · Zbl 1175.94009
[3] Becker, S. R.; Bobin, J.; Candès Nesta, E. J., A fast and accurate first-order method for sparse recovery, SIAM J. Imaging Sci., 4, 1, 1-39 (2011) · Zbl 1209.90265
[4] Becker, S. R.; Bobin, J.; Candès, E. J., Nesta, URL
[5] Becker, S. R.; Candès, E. J.; Grant, M. C., Templates for convex cone problems with applications to sparse signal recovery, Math. Program. Comput., 3, 3, 165 (2011) · Zbl 1257.90042
[6] Becker, S. R.; Candès, E. J.; Grant, M. C., Tfocs, URL
[7] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1, 1-122 (2011) · Zbl 1229.90122
[8] Cai, T. T.; Xu, G.; Zhang, J., On recovery of sparse signals via \(\ell_1\)-minimization, IEEE Trans. Inf. Theory, 55, 7, 3388-3397 (2009) · Zbl 1367.94081
[9] Candès, E. J., The restricted isometry property and its implications for compressed sensing, C. R. Math., 346, 9-10, 589-592 (2008) · Zbl 1153.94002
[10] Candès, E. J.; Romberg, J., l1-magic: recovery of sparse signals via convex programming, 4, 14 (2005)
[11] Candès, E. J.; Romberg, J. K.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017
[12] Candès, E. J.; Romberg, J. K.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59, 8, 1207-1223 (2006) · Zbl 1098.94009
[13] Candès, E. J.; Tao, T., Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 12, 4203-4215 (2005) · Zbl 1264.94121
[14] Candès, E. J.; Tao, T., Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inf. Theory, 52, 12, 5406-5425 (2006) · Zbl 1309.94033
[15] Candès, E. J.; Tao, T., The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\), Ann. Stat., 2313-2351 (2007) · Zbl 1139.62019
[16] Chambolle, A.; Pock, T., A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40, 1, 120-145 (2011) · Zbl 1255.68217
[17] Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM Rev., 43, 1, 129-159 (2001) · Zbl 0979.94010
[18] Chen, P.; Huang, J.; Zhang, X., A primal-dual fixed point algorithm for convex separable minimization with applications to image restoration, Inverse Probl., 29, 2, Article 025011 pp. (2013) · Zbl 1279.65075
[19] Combettes, P. L.; Wajs, V. R., Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4, 4, 1168-1200 (2005) · Zbl 1179.94031
[20] Donoho, D. L., De-noising by soft-thresholding, IEEE Trans. Inf. Theory, 41, 3, 613-627 (1995) · Zbl 0820.62002
[21] Donoho, D. L., Compressed sensing, IEEE Trans. Inf. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016
[22] Eckstein, J.; Bertsekas, D. P., On the Douglas-Rachford Splitting Method and the Proximal Point Algorithm for Maximal Monotone Operators (1992), Springer-Verlag, New York, Inc. · Zbl 0765.90073
[23] J. Eckstein, W. Yao, Augmented Lagrangian and Alternating Direction Methods for Convex Optimization: A Tutorial and Some Illustrative Computational Results, Rutcor Research Reports 32.; J. Eckstein, W. Yao, Augmented Lagrangian and Alternating Direction Methods for Convex Optimization: A Tutorial and Some Illustrative Computational Results, Rutcor Research Reports 32.
[24] Efron, B.; Hastie, T.; Johnstone, I.; Tibshirani, R., Least angle regression, Ann. Stat., 32, 2, 407-499 (2004) · Zbl 1091.62054
[25] Elad, M., Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing (2010), Springer Science & Business Media · Zbl 1211.94001
[26] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2, 1, 17-40 (1976) · Zbl 0352.65034
[27] Hale, E. T.; Yin, W.; Zhang, Y., Fixed-point continuation for \(\ell_1\)-minimization: methodology and convergence, SIAM J. Optim., 19, 3, 1107-1130 (2008) · Zbl 1180.65076
[28] He, B.; Yuan, X., Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective, SIAM J. Imaging Sci., 5, 1, 119-149 (2012) · Zbl 1250.90066
[29] Li, Q.; Shen, L.; Xu, Y.; Zhang, N., Multi-step fixed-point proximity algorithms for solving a class of optimization problems arising from image processing, Adv. Comput. Math., 41, 2, 387-422 (2015) · Zbl 1326.65069
[30] Lu, Z.; Pong, T. K.; Zhang, Y., An alternating direction method for finding Dantzig selectors, Comput. Stat. Data Anal., 56, 12, 4037-4046 (2012) · Zbl 1255.62096
[31] Micchelli, C. A.; Shen, L.; Xu, Y., Proximity algorithms for image models: denoising, Inverse Probl., 27, 4, Article 045009 pp. (2011) · Zbl 1216.94015
[32] Nesterov, Y., Smooth minimization of non-smooth functions, Math. Program., 103, 1, 127-152 (2005) · Zbl 1079.90102
[33] Osher, S.; Burger, M.; Goldfarb, D.; Xu, J.; Yin, W., An iterative regularization method for total variation-based image restoration, Multiscale Model. Simul., 4, 2, 460-489 (2005) · Zbl 1090.94003
[34] Osher, S.; Mao, Y.; Dong, B.; Yin, W., Fast linearized Bregman iteration for compressive sensing and sparse denoising, Math. Comput., 8, 1, 93-111 (2010) · Zbl 1190.49040
[35] Rockafellar, R. T., Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 5, 877-898 (1976) · Zbl 0358.90053
[36] Rockafellar, R. T., Augmented lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1, 2, 97-116 (1976) · Zbl 0402.90076
[37] Rockafellar, R. T., Convex Analysis (2015), Princeton University Press
[38] Shefi, R.; Teboulle, M., Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization, SIAM J. Optim., 24, 24, 269-297 (2014) · Zbl 1291.90176
[39] Tibshirani, R., Regression shrinkage and selection via the lasso, J. R. Stat. Soc. B, 267-288 (1996) · Zbl 0850.62538
[40] Van Den Berg, E.; Friedlander, M. P., Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 2, 890-912 (2008) · Zbl 1193.49033
[41] Wang, X.; Yuan, X., The linearized alternating direction method of multipliers for Dantzig selector, SIAM J. Sci. Comput., 34, 5, A2792-A2811 (2012) · Zbl 1263.90061
[42] Yang, J.; Zhang, Y., Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing, SIAM J. Sci. Comput., 33, 1, 250-278 (2011) · Zbl 1256.65060
[43] Yin, W., Analysis and generalizations of the linearized Bregman method, SIAM J. Imaging Sci., 3, 4, 856-877 (2009) · Zbl 1211.68491
[44] Yin, W.; Osher, S.; Goldfarb, D.; Darbon, J., Bregman iterative algorithms for \(\ell_1\)-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1, 1, 143-168 (2008) · Zbl 1203.90153
[45] Zhang, X.; Burger, M.; Osher, S., A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput., 46, 1, 20-46 (2011) · Zbl 1227.65052
[46] Zhang, Y.; Deng, W.; Yang, J.; Yin, W., Yall1, URL
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.