# 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
PDCO
Full Text:
##### References:
  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  Chen, Scott Shaobing; Donoho, David L.; Saunders, Michael A., Atomic decomposition by basis pursuit, SIAM Rev., 43, 1, 129-159 (2001) · Zbl 0979.94010  Tibshirani, Robert, Regression shrinkage and selection via the lasso, J. R. Stat. Soc., 73, 3, 267-288 (2011) · Zbl 0850.62538  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  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  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)  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)  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  Majumdar, Angshul; Ward, Rabab K., Compressed sensing of color images, Signal Process., 90, 12, 3122-3127 (2010) · Zbl 1197.94089  Chartrand, Rick, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14, 10, 707-710 (2007)  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  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)  Zhang, Tong, Analysis of multi-stage convex relaxation for sparse regularization, J. Mach. Learn. Res., 11, 1081-1107 (Mar 2010)  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  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  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)  Candes, Emmanuel J.; Tao, Terence, Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 12, 4203-4215 (2005) · Zbl 1264.94121  Sun, Qiyu, Recovery of sparsest signals via $$\ell_q$$-minimization, Appl. Comput. Harmon. Anal., 32, 3, 329-341 (2012) · Zbl 1266.94017  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  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  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  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  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  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  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  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  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)  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  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  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  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  Adams, Robert A.; Fournier, John JF, Sobolev Spaces, vol. 140 (2003), Elsevier  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  Blumensath, Thomas; Davies, Mike E., Iterative thresholding for sparse approximations, J. Fourier Anal. Appl., 14, 5-6, 629-654 (2008) · Zbl 1175.94060  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  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  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)  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)  Tyrrell Rockafellar, R.; Wets, Roger J-B., Variational Analysis, vol. 317 (2009), Springer Science & Business Media  Ł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  Krzysztof, Kurdyka, On gradients of functions definable in o-minimal structures, Ann. Inst. Fourier, 48, 3, 769-783 (1998) · Zbl 0934.32009  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  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  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  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  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  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.