×

zbMATH — the first resource for mathematics

The \(\ell_{2,q}\) regularized group sparse optimization: lower bound theory, recovery bound and algorithms. (English) Zbl 1448.94058
This paper deals with the classical problem of signal recovery, namely to restore a vector \(x^{0}\in \mathbb{R}^{N}\) from a noisy observation \(d\). This problem is modeled as \(d=Ax^0+\xi\) where \(A\in \mathbb{R}^{M\times N}\) is the measurement matrix and \(\xi \in \mathbb{R}^M\) represents the measurement error. The authors consider the case where the data to be restored have a natural structure.
In particular, they assume that vectors \(x=(x_1,x_2,\ldots ,x_N)\in \mathbb{R}^N\) have a predefined group structure \(x=(x_{\mathcal{G}_1},x_{\mathcal{G}_2},\ldots ,x_{\mathcal{G}_n}),\) where \(\mathcal{G}_i\subset \{1,\ldots ,n\}\) and \(x_{\mathcal{G}_i}\) denotes the \(i\)-th group of \(x\) for \(i\in \{1,2,\ldots,n\}\). In this case, the group sparsity of \(x\) is better measured by a nonconvex \(\ell _{p,q}\) “norm”, defined by \(||x||_{p,q}:=\left( \sum_{i=1}^n ||x_{\mathcal{G}i}||_p^q \right)^{1/q},\) where \(p\geq 1\) and \(q\in (0,1)\). The authors consider the case \(p=2\) and focus on the minimization of the \(\ell _{p,q}\) regularization: \( \underset{x\in \mathbb{R}^{N}}{\mathrm{min}}\,\left\{||Ax-d||^{2}+||x||_{2,q}^{q}\right\}.\)
They provide sufficient conditions for stationary points to be local minimizers and give a uniform lower bound for nonzero groups of local minimizers. They also propose a new IRLS (iteratively reweighted least square) algorithm with thresholding together with an error bound analysis. This new algorithm compares favorably with the classical IRLS algorithm with smoothing in both global convergence and computational efficiency. The paper also contains some numerical experiments.
MSC:
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
62J07 Ridge regression; shrinkage estimators (Lasso)
90C26 Nonconvex programming, global optimization
Software:
PDCO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Daubechies, Ingrid; Defrise, Michel; De Mol, Christine, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pure Appl. Math., 57, 11, 1413-1457 (2004), A Journal Issued by the Courant Institute of Mathematical Sciences · Zbl 1077.65055
[2] Chen, Scott Shaobing; Donoho, David L.; Saunders, Michael A., Atomic decomposition by basis pursuit, SIAM Rev., 43, 1, 129-159 (2001) · Zbl 0979.94010
[3] Tibshirani, Robert, Regression shrinkage and selection via the lasso, J. R. Stat. Soc., 73, 3, 267-288 (2011) · Zbl 0850.62538
[4] Yuan, Ming; Lin, Yi, Model selection and estimation in regression with grouped variables, J. R. Stat. Soc., Ser. B, Stat. Methodol., 68, 1, 49-67 (2006) · Zbl 1141.62030
[5] Erickson, Stephen; Sabatti, Chiara, Empirical Bayes estimation of a sparse vector of gene expression changes, Stat. Appl. Genet. Mol. Biol., 4, 1, Article 22 pp. (2005) · Zbl 1081.62093
[6] Parvaresh, Farzad; Vikalo, Haris; Misra, Sidhant; Hassibi, Babak, Recovering sparse signals using sparse measurement matrices in compressed dna microarrays, IEEE J. Sel. Top. Signal Process., 2, 3, 275-285 (2008)
[7] Usman, M.; Prieto, C.; Schaeffter, T.; Batchelor, P. G., k-t group sparse: a method for accelerating dynamic mri, Magn. Reson. Med., 66, 4, 1163 (2011)
[8] Malioutov, Dmitry; Cetin, Müjdat; Willsky, Alan S., A sparse signal reconstruction perspective for source localization with sensor arrays, IEEE Trans. Signal Process., 53, 8, 3010-3022 (2005) · Zbl 1370.94191
[9] Majumdar, Angshul; Ward, Rabab K., Compressed sensing of color images, Signal Process., 90, 12, 3122-3127 (2010) · Zbl 1197.94089
[10] Chartrand, Rick, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14, 10, 707-710 (2007)
[11] Chartrand, Rick; Yin, Wotao, Iteratively reweighted algorithms for compressive sensing, (IEEE International Conference on Acoustics, Speech and Signal Processing. ICASSP 2008 (2008), IEEE), 3869-3872
[12] Xu, Zongben; Chang, Xiangyu; Xu, Fengmin; Zhang, Hai, \( l_{1 / 2}\) regularization: a thresholding representation theory and a fast solver, IEEE Trans. Neural Netw. Learn. Syst., 23, 7, 1013 (2012)
[13] Zhang, Tong, Analysis of multi-stage convex relaxation for sparse regularization, J. Mach. Learn. Res., 11, 1081-1107 (Mar 2010)
[14] Foucart, Simon; Lai, Mingjun, Sparsest solutions of underdetermined linear systems via \(\ell_q\)-minimization for \(0 < q < 1\), Appl. Comput. Harmon. Anal., 26, 3, 395-407 (2009) · Zbl 1171.90014
[15] Hu, Yaohua; Li, Chong; Meng, Kaiwen; Qin, Jing; Yang, Xiaoqi, Group sparse optimization via \(\ell_{p , q}\) regularization, J. Mach. Learn. Res., 18, 1, 960-1011 (2017) · Zbl 1433.90202
[16] Rakotomamonjy, Alain; Flamary, Rémi; Gasso, Gilles; Canu, Stéphane, \( \ell_p - \ell_q\) penalty for sparse linear and sparse multiple kernel multitask learning, IEEE Trans. Neural Netw., 22, 8, 1307-1320 (2011)
[17] Candes, Emmanuel J.; Tao, Terence, Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 12, 4203-4215 (2005) · Zbl 1264.94121
[18] Sun, Qiyu, Recovery of sparsest signals via \(\ell_q\)-minimization, Appl. Comput. Harmon. Anal., 32, 3, 329-341 (2012) · Zbl 1266.94017
[19] Candes, Emmanuel J.; Romberg, Justin; Tao, Terence, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017
[20] Candes, Emmanuel J.; Romberg, Justin K.; Tao, Terence, Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59, 8, 1207-1223 (2006) · Zbl 1098.94009
[21] Cohen, Albert; Dahmen, Wolfgang; Devore, Ronald, Compressed sensing and best k-term approximation, J. Am. Math. Soc., 22, 1, 211-231 (2009) · Zbl 1206.94008
[22] Candes, Emmanuel J., The restricted isometry property and its implications for compressed sensing, C. R. Math., 346, 9-10, 589-592 (2008) · Zbl 1153.94002
[23] Tony Cai, T.; Wang, Lie; Xu, Guangwu, Shifting inequality and recovery of sparse signals, IEEE Trans. Signal Process., 58, 3, 1300-1308 (2009) · Zbl 1392.94117
[24] Bickel, Peter J.; Ritov, Ya’acov; Tsybakov Alexandre, B., Simultaneous analysis of lasso and Dantzig selector, Ann. Stat., 37, 4, 1705-1732 (2009) · Zbl 1173.62022
[25] Ahsen, M. Eren; Vidyasagar, Mathukumalli, Error bounds for compressed sensing algorithms with group sparsity: a unified approach, Appl. Comput. Harmon. Anal., 43, 2, 212-232 (2017) · Zbl 06763901
[26] Eldar, Yonina C.; Mishali, Moshe, Robust recovery of signals from a structured union of subspaces, IEEE Trans. Inf. Theory, 55, 11, 5302-5316 (2009) · Zbl 1367.94087
[27] Wang, Yao; Wang, Jianjun; Xu, Zongben, On recovery of block-sparse signals via mixed norm minimization, EURASIP J. Adv. Signal Process., 2013, 1, 76 (2013)
[28] Xue, Yunhua; Feng, Yanfei; Wu, Chunlin, An efficient and globally convergent algorithm for \(\ell_{p , q}- \ell_r\) model in group sparse optimization, Commun. Math. Sci., 18, 1, 227-258 (2020) · Zbl 1436.49037
[29] Daubechies, Ingrid; DeVore, Ronald; Fornasier, Massimo; Güntürk, C. Sinan, Iteratively reweighted least squares minimization for sparse recovery, Commun. Pure Appl. Math., 63, 1, 1-38 (2010) · Zbl 1202.65046
[30] Lai, Mingjun; Wang, Jingyue, An unconstrained \(\ell_q\) minimization with \(0 < q \leq 1\) for sparse solution of underdetermined linear systems, SIAM J. Optim., 21, 1, 82-101 (2011) · Zbl 1220.65051
[31] Lai, Mingjun; Xu, Yangyang; Yin, Wotao, Improved iteratively reweighted least squares for unconstrained smoothed \(\ell_q\) minimization, SIAM J. Numer. Anal., 51, 2, 927-957 (2013) · Zbl 1268.49038
[32] Adams, Robert A.; Fournier, John JF, Sobolev Spaces, vol. 140 (2003), Elsevier
[33] Chen, Xiaojun; Xu, Fengmin; Ye, Yinyu, Lower bound theory of nonzero entries in solutions of \(\ell_2- \ell_p\) minimization, SIAM J. Sci. Comput., 32, 5, 2832-2852 (2010) · Zbl 1242.90174
[34] Blumensath, Thomas; Davies, Mike E., Iterative thresholding for sparse approximations, J. Fourier Anal. Appl., 14, 5-6, 629-654 (2008) · Zbl 1175.94060
[35] Meier, Lukas; Van De Geer, Sara; Bühlmann, Peter, The group lasso for logistic regression, J. R. Stat. Soc., Ser. B, Stat. Methodol., 70, 1, 53-71 (2008) · Zbl 1400.62276
[36] Liu, Zhifang; Wu, Chunlin; Zhao, Yanan, A new globally convergent algorithm for non-Lipschitz \(\ell_p - \ell_q\) minimization, Adv. Comput. Math., 45, 3, 1369-1399 (2019) · Zbl 1415.49022
[37] Zeng, Chao; Jia, Rui; Wu, Chunlin, An iterative support shrinking algorithm for non-Lipschitz optimization in image restoration, J. Math. Imaging Vis., 61, 1, 122-139 (Jan 2019)
[38] Attouch, Hedy; Bolte, Jérôme; Svaiter, Benar Fux, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., 137, 1, 91-129 (Feb 2013)
[39] Tyrrell Rockafellar, R.; Wets, Roger J-B., Variational Analysis, vol. 317 (2009), Springer Science & Business Media
[40] Łojasiewicz, Stanislaw, Une propriété topologique des sous-ensembles analytiques réels, Les équations aux dérivées partielles, 117, 87-89 (1963) · Zbl 0234.57007
[41] Krzysztof, Kurdyka, On gradients of functions definable in o-minimal structures, Ann. Inst. Fourier, 48, 3, 769-783 (1998) · Zbl 0934.32009
[42] Bolte, Jérôme; Daniilidis, Aris; Lewis, Adrian, The łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17, 4, 1205-1223 (2007) · Zbl 1129.26012
[43] Bolte, Jérôme; Daniilidis, Aris; Lewis, Adrian; Shiota, Masahiro, Clarke subgradients of stratifiable functions, SIAM J. Optim., 18, 2, 556-572 (2007) · Zbl 1142.49006
[44] Attouch, Hédy; Bolte, Jérôme, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., 116, 1, 5-16 (2009) · Zbl 1165.90018
[45] Attouch, Hédy; Bolte, Jérôme; Redont, Patrick; Soubeyran, Antoine, Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality, Math. Oper. Res., 35, 2, 438-457 (2010) · Zbl 1214.65036
[46] Bolte, Jérôme; Sabach, Shoham; Teboulle, Marc, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146, 1-2, 459-494 (2014) · Zbl 1297.90125
[47] Van den Dries, Lou; Miller, Chris, Geometric categories and o-minimal structures, Duke Math. J., 84, 2, 497-540 (1996) · Zbl 0889.03025
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.