\(l_1\)-\(l_2\) regularization of split feasibility problems. (English) Zbl 1395.49014
Summary: Numerous problems in signal processing and imaging, statistical learning and data mining, or computer vision can be formulated as optimization problems which consist in minimizing a sum of convex functions, not necessarily differentiable, possibly composed with linear operators and that in turn can be transformed to split feasibility problems (SFP); see for example [Y. Censor and T. Elfving, Numer. Algorithms 8, No. 2–4, 221–239 (1994; Zbl 0828.65065)]. Each function is typically either a data fidelity term or a regularization term enforcing some properties on the solution; see for example [C. Chaux et al., SIAM J. Imaging Sci. 2, No. 2, 730–762 (2009; Zbl 1186.68520)] and references therein. In this paper, we are interested in split feasibility problems which can be seen as a general form of \(Q\)-Lasso introduced in [M. A. Alghamdi et al., Abstr. Appl. Anal. 2013, Article ID 250943, 8 p. (2013; Zbl 1359.94052)] that extended the well-known Lasso of R. Tibshirani [J. R. Stat. Soc., Ser. B 58, No. 1, 267–288 (1996; Zbl 0850.62538)]. \(Q\) is a closed convex subset of a Euclidean \(m\)-space, for some integer \(m\geq 1\), that can be interpreted as the set of errors within given tolerance level when linear measurements are taken to recover a signal/image via the Lasso. Inspired by recent works by Y. Lou and M. Yan [J. Sci. Comput. 74, No. 2, 767–785 (2018; Zbl 1390.90447)] and Z. Xu et al. [“\(L_{1/2}\) regularization: a thresholding representation theory and a fast solver”, IEEE Trans. Neural Networks Learn. Syst. 23, No. 7, 1013–1027 (2012; doi:10.1109/tnnls.2012.2197412)]], we are interested in a nonconvex regularization of SFP and propose three split algorithms for solving this general case. The first one is based on the DC (difference of convex) algorithm (DCA) introduced by Pham Dinh Tao, the second one is nothing else than the celebrate forward-backward algorithm, and the third one uses a method introduced by H. Mine and M. Fukushima [J. Optim. Theory Appl. 33, 9–23 (1981; Zbl 0422.90070)]. It is worth mentioning that the SFP model a number of applied problems arising from signal/image processing and specially optimization problems for intensity-modulated radiation therapy (IMRT) treatment planning; see for example [Y. Censor et al., “A unified approach for inversion problems in intensity-modulated radiation therapy”, Phys. Med. Biol. 51, No. 10, 2353–2365 (2006; doi:10.1088/0031-9155/51/10/001)].
MSC:
| 49J53 | Set-valued and variational analysis |
| 65K10 | Numerical optimization and variational techniques |
| 49M37 | Numerical methods based on nonlinear programming |
| 90C25 | Convex programming |
Keywords:
Q-Lasso; split feasibility; soft-thresholding; regularization; DCA algorithm; forward-backward iterations; Mine-Fukushima algorithm; Douglas-Rachford algorithmCitations:
Zbl 0828.65065; Zbl 1186.68520; Zbl 1359.94052; Zbl 0850.62538; Zbl 0422.90070; Zbl 1390.90447Software:
PDCOReferences:
| [1] | Alghamdi, M.A., Ali Alghamdi, M., Shahzad, N., Naseer, H.-K. X.: Properties and Iterative Methods for the Q-Lasso, Abstract and Applied Analysis. Article ID 250943, 8 pages (2013) · Zbl 1359.94052 |
| [2] | Byrne, C, Iterative oblique projection onto convex sets and the split feasibility problem, Inverse Prob., 18, 441-453, (2002) · Zbl 0996.65048 · doi:10.1088/0266-5611/18/2/310 |
| [3] | Byrne, C, A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Prob., 20, 103â-120, (2004) · Zbl 1051.65067 · doi:10.1088/0266-5611/20/1/006 |
| [4] | Censor, Y; Bortfeld, T; Martin, B; Trofimov, A, A unified approach for inversion problems in intensity-modulated radiation therapy, Phys. Med. Biol., 51, 2353-2365, (2006) · doi:10.1088/0031-9155/51/10/001 |
| [5] | Censor, Y; Elfving, T, A multiprojection algorithm using Bregman projections in a product space, Numer. Algorithms, 8, 221-239, (1994) · Zbl 0828.65065 · doi:10.1007/BF02142692 |
| [6] | Censor, Y; Gibali, A; Lenzen, F; Schnorr, Ch, The implicit convex feasibility problem and its application to adaptive image denoising, J. Comput. Math., 34, 610-625, (2016) · Zbl 1374.90305 · doi:10.4208/jcm.1606-m2016-0581 |
| [7] | Chartrand, R, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process Lett., 14, 707-710, (2007) · doi:10.1109/LSP.2007.898300 |
| [8] | Chen, S; Donoho, D; Saunders, M, Atomic decomposition by basis pursuit, SIAM J. Comput., 20, 33-61, (1998) · Zbl 0919.94002 · doi:10.1137/S1064827596304010 |
| [9] | Chaux, C; Pesquet, J-C; Pustelnik, N, Nested iterative algorithms for convex constrained image recovery problems, SIAM J. Imag. Sci., 2, 730-762, (2009) · Zbl 1186.68520 · doi:10.1137/080727749 |
| [10] | Chen, SS; Donoho, DL; Saunders, MA, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 33-61, (1998) · Zbl 0919.94002 · doi:10.1137/S1064827596304010 |
| [11] | Combettes, PL; Pesquet, J-C, A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery, IEEE J. Sel. Top. Sign. Proces., 1, 564-574, (2007) · doi:10.1109/JSTSP.2007.910264 |
| [12] | Condat, L, A generic proximal algorithm for convex optimization: application to total variation minimization, IEEE Signal Process Lett., 21, 985-989, (2014) · doi:10.1109/LSP.2014.2322123 |
| [13] | Donoho, D, Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306, (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582 |
| [14] | Esser, E; Lou, Y; Xin, J, A method for finding structured sparse solutions to non-negative least squares problems with applications, SIAM J. Imag. Sci., 6, 2010-2046, (2013) · Zbl 1282.90239 · doi:10.1137/13090540X |
| [15] | Lou, Y., Yan, M.: Fast \(l\)_{1} − \(l\)_{2} Minimization via a proximal operator. arXiv:1609.09530 (2017) · Zbl 0919.94002 |
| [16] | Micchelli, ChA; Shen, L; Xu, Y; Zeng, X, Proximity algorithms for the L1/TV image denoising model, Adv. Comput. Math., 38, 401-426, (2013) · Zbl 1275.65014 · doi:10.1007/s10444-011-9243-y |
| [17] | Mine, H; Fukushima, M, A minimization method for the sum of a convex function and a continuously differentiable function, J. Optim. Theory Appl., 33, 9-23, (1981) · Zbl 0422.90070 · doi:10.1007/BF00935173 |
| [18] | Moudafi, A.: About proximal algorithms for Q-Lasso, Thai Mathematical Journal (2016) · Zbl 1385.49008 |
| [19] | Natarajan, BK, Sparse approximate solutions to linear systems, SIAM J. Comput., 24, 227-234, (1995) · Zbl 0827.68054 · doi:10.1137/S0097539792240406 |
| [20] | Qu, B; Xiu, N, A note on the CQ algorithm for the split feasibility problem, Inverse Prob., 21, 1655-1665, (2005) · Zbl 1080.65033 · doi:10.1088/0266-5611/21/5/009 |
| [21] | Tang, Y.-C., Liu, L.-W., Gibali, A.: Note on the modified relaxation CQ algorithm for the split feasibility problem. Optim. Lett., 1-14. https://doi.org/10.1007/s11590-017-1148-3 (2017) · Zbl 0828.65065 |
| [22] | Tibshirani, R, Regression shrinkage and selection via the lasso, J. R. Stat. Soc. Ser. B, 58, 267-288, (1996) · Zbl 0850.62538 |
| [23] | Yin, P; Lou, Y; He, Q; Xin, J, Minimization of l1−2 for compressed sensing, SIAM J. Sci. Comput., 37, 536-563, (2015) · Zbl 1316.90037 · doi:10.1137/140952363 |
| [24] | Xu, Z; Chang, X; Xu, F; Zhang, H, L1−2 regularization: a thresholding representation theory and a fast solver, IEEE Trans. Neural Netw. Learn. Syst., 23, 1013-1027, (2012) · doi:10.1109/TNNLS.2012.2197412 |
| [25] | Zeng, X; Figueiredo, MA-T, Solving OSCAR regularization problems by fast approximate proximal splittings algorithms, Digital Signal Process., 31, 124-135, (2014) · doi:10.1016/j.dsp.2014.03.010 |
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.
