Abstract
We propose a general formulation of nonconvex and nonsmooth sparse optimization problems with convex set constraint, which can take into account most existing types of nonconvex sparsity-inducing terms, bringing strong applicability to a wide range of applications. We design a general algorithmic framework of iteratively reweighted algorithms for solving the proposed nonconvex and nonsmooth sparse optimization problems, which solves a sequence of weighted convex regularization problems with adaptively updated weights. First-order optimality condition is derived and global convergence results are provided under loose assumptions, making our theoretical results a practical tool for analyzing a family of various reweighted algorithms. The effectiveness and efficiency of our proposed formulation and the algorithms are demonstrated in numerical experiments on various sparse optimization problems.
Similar content being viewed by others
References
Ba, D., Babadi, B., Purdon, P.L., Brown, E.N.: Convergence and stability of iteratively re-weighted least squares algorithms. IEEE Trans. Signal Process. 62(1), 183–195 (2014)
Bach, F., Jenatton, R., Mairal, J., Obozinski, G., et al.: Optimization with sparsity-inducing penalties. Foundations and Trends®. Mach. Learn. 4(1), 1–106 (2012)
Bazaraa, M.S., Goode, J., Nashed, M.Z.: On the cones of tangents with applications to mathematical programming. J. Optim. Theory Appl. 13(4), 389–426 (1974)
Bian, W., Chen, X.: Optimality and complexity for constrained optimization problems with nonconvex regularization. Math. Oper. Res. 42(4), 1063–1084 (2017)
Bradley, P.S., Mangasarian, O.L., Street, W.N.: Feature selection via mathematical programming. INFORMS J. Comput. 10(2), 209–217 (1998)
Burke, J.V., Curtis, F.E., Wang, H., Wang, J.: Iterative reweighted linear least squares for exact penalty subproblems on product sets. SIAM J. Optim. 25(1), 261–294 (2015)
Candès, E.J., Wakin, M.B.: An introduction to compressive sampling. IEEE Signal Process. Mag. 25(2), 21–30 (2008)
Candes, E.J., Wakin, M.B., Boyd, S.P.: Enhancing sparsity by reweighted 1 minimization. J. Fourier Anal. Appl. 14(5–6), 877–905 (2008)
Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: Acoustics, speech and signal processing, 2008. ICASSP 2008. IEEE international conference on, pp. 3869–3872. IEEE (2008)
Chen, X., Zhou, W.: Convergence of Reweighted l1 Minimization Algorithms and Unique Solution of Truncated lp Minimization. The Hong Kong Polytechnic University, Department of Applied Mathematics (2010)
Daubechies, I., DeVore, R., Fornasier, M., Güntürk, C.S.: Iteratively reweighted least squares minimization for sparse recovery. Commun. Pure Appl. Math. 63(1), 1–38 (2010)
Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348–1360 (2001)
Fazel, M., Hindi, H., Boyd, S.P.: Log-det heuristic for matrix rank minimization with applications to hankel and euclidean distance matrices. In: American control conference, 2003. Proceedings of the 2003, vol. 3, pp. 2156–2162. IEEE (2003)
Grant, M., Boyd, S., Ye, Y.: CVX: Matlab software for disciplined convex programming (2008). (Web page and software.) http://stanford.edu/~boyd/cvx (2015)
Harrell, F.E.: Ordinal logistic regression. In: Regression modeling strategies, pp. 311–325. Springer (2015)
Hastie, T., Tibshirani, R., Wainwright, M.: Statistical Learning with Sparsity: The Lasso and Generalizations. CRC Press, Boca Raton (2015)
Holland, P.W., Welsch, R.E.: Robust regression using iteratively reweighted least-squares. Commun. Stat. Theory Methods 6(9), 813–827 (1977)
Hu, Y., Li, C., Meng, K., Qin, J., Yang, X.: Group sparse optimization via \(\ell _{p, q}\) regularization. J. Mach. Learn. Res. 18(1), 960–1011 (2017)
Khajehnejad, M.A., Dimakis, A.G., Xu, W., Hassibi, B.: Sparse recovery of nonnegative signals with minimal expansion. IEEE Trans. Signal Process. 59(1), 196–208 (2011)
Kruger, A.Y.: \(\varepsilon \)-semidifferentials and \(\varepsilon \)-normal elements. Depon. VINITI 1331,(1981)
Kruger, A.Y.: On fréchet subdifferentials. J. Math. Sci. 116(3), 3325–3358 (2003)
Lai, M.J., Wang, J.: An unconstrained \(\ell _q\) minimization with \(0\le q \le 1\) for sparse solution of underdetermined linear systems. SIAM J. Optim. 21(1), 82–101 (2011)
Lanza, A., Morigi, S., Sgallari, F.: Convex image denoising via non-convex regularization. In: International Conference on Scale Space and Variational Methods in Computer Vision. Springer , pp. 666–677 (2015)
Ling, Q., Wen, Z., Yin, W.: Decentralized jointly sparse optimization by reweighted \(\ell _q\) minimization. IEEE Trans. Signal Process. 61(5), 1165–1170 (2013)
Liu, L., Larsson, E.G., Yu, W., Popovski, P., Stefanovic, C., de Carvalho, E.: Sparse signal processing for grant-free massive connectivity: a future paradigm for random access protocols in the internet of things. IEEE Signal Process. Mag. 35(5), 88–99 (2018)
Lobo, M.S., Fazel, M., Boyd, S.: Portfolio optimization with linear and fixed transaction costs. Ann. Oper. Res. 152(1), 341–365 (2007)
Lu, C., Wei, Y., Lin, Z., Yan, S.: Proximal iteratively reweighted algorithm with multiple splitting for nonconvex sparsity optimization. In: AAAI, pp. 1251–1257 (2014)
Lu, Z.: Iterative reweighted minimization methods for \(\ell _p\) regularized unconstrained nonlinear programming. Math. Program. 147(1–2), 277–307 (2014)
Lu, Z., Zhang, Y., Lu, J.: \(\ell _p \) regularized low-rank approximation via iterative reweighted singular value minimization. Comput. Optim. Appl. 68(3), 619–642 (2017)
Malek-Mohammadi, M., Babaie-Zadeh, M., Skoglund, M.: Iterative concave rank approximation for recovering low-rank matrices. IEEE Trans. Signal Process. 62(20), 5213–5226 (2014)
Miosso, C.J., von Borries, R., Argaez, M., Velázquez, L., Quintero, C., Potes, C.: Compressive sensing reconstruction with prior information by iteratively reweighted least-squares. IEEE Trans. Signal Process. 57(6), 2424–2431 (2009)
Ochs, P., Dosovitskiy, A., Brox, T., Pock, T.: On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision. SIAM J. Imaging Sci. 8(1), 331–372 (2015)
Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Siam, New Delhi (1970)
Qin, Z., Fan, J., Liu, Y., Gao, Y., Li, G.Y.: Sparse representation for wireless communications: a compressive sensing approach. IEEE Signal Process. Mag. 35(3), 40–58 (2018)
Rockafellar, R.T., Wets, R.J.B.: Variational Analysis, vol. 317. Springer Science & Business Media, New York (2009)
Shi, Y., Cheng, J., Zhang, J., Bai, B., Chen, W., Letaief, K.B.: Smoothed \(l_p\)-minimization for green cloud-ran with user admission control. IEEE J. Sel. Areas Commun. 34(4), 1022–1036 (2016)
Shi, Y., Zhang, J., Chen, W., Letaief, K.B.: Generalized sparse and low-rank optimization for ultra-dense networks. IEEE Commun. Mag. 56(6), 42–48 (2018)
Shi, Y., Zhang, J., Letaief, K.B.: Group sparse beamforming for green cloud-ran. IEEE Trans. Wirel. Commun. 13(5), 2809–2823 (2014)
Street, J.O., Carroll, R.J., Ruppert, D.: A note on computing robust regression estimates via iteratively reweighted least squares. Am. Stat. 42(2), 152–154 (1988)
Wainwright, M.J.: Structured regularizers for high-dimensional problems: statistical and computational issues. Annu. Rev. Stat. Appl. 1, 233–253 (2014)
Wang, H., Li, D.H., Zhang, X.J., Wu, L.: Optimality conditions for the constrained \( \ell _p \)-regularization. Optimization 64(10), 2183–2197 (2015)
Weston, J., Elisseeff, A., Schölkopf, B., Tipping, M.: Use of the zero-norm with linear models and kernel methods. J. Mach. Learn. Res. 3, 1439–1461 (2003)
Zhang, C.H.: Penalized linear unbiased selection. In: Department of Statistics and Bioinformatics. Rutgers University, New Jersey (2007)
Lai, M.J., Xu, Y.Y., Yin, W.T.: Improved iteratively reweighted least squares for unconstrained smoothed \(ell\_q\) minimization. SIAM J. Numer. Anal. 51(2), 927–957 (2013)
Liu, T., Pong, T.K., Takeda, A.: A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems. Math. Program. 176(1), 339–367 (2019)
Cao, W.F., Sun, J., Xu, Z.B.: Fast image deconvolution using closed-form thresholding formulas of \(L_q\) (\(q= 1/2, 2/3\)) regularization. J. Vis. Commun. Image Represent. 24(1), 31–41 (2013)
Ahn, M.J., Pang, J.S., Xin, J.: Difference-of-convex learning: directional stationarity, optimality, and sparsity. SIAM J. Optim. 27(3), 1637–1665 (2017)
Cao, S.S., Huo, X.M., Pang, J.S.: A unifying framework of high-dimensional sparse estimation with difference-of-convex (DC). Regularizations 1812(07130), 31–41 (2018). arXiv:1812.07130
Acknowledgements
Hao Wang’s work was supported by National Natural Science Foundation of China [12001367] and the Natural Science Foundation of Shanghai [21ZR1442800]. Yaohua Hu’s work was supported in part by the National Natural Science Foundation of China [12071306, 11871347], Natural Science Foundation of Guangdong Province of China [2019A1515011917, 2020B1515310008, 2020A1515010372], and Natural Science Foundation of Shenzhen [JCYJ20190808173603590].
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
A implementation details of SDCAM
A implementation details of SDCAM
In this section, we provide the details of solving problem (16) by using SDCAM. By denoting
and
we can reformulate problem (16) as
Then this problem can be solved by the SDCAM [45]. They approximate F by its Moreau envelope at each iteration. More specifically, at iteration k, they solve the following approximate problem
where \(e_{\lambda _k} P_1({\mathbf {v}})\) is the Moreau envelope of \( P_1({\mathbf {v}})\) with parameter \(\lambda _k\), which takes the form
The SDCAM drives the parameter \(\lambda _k\) to 0 and solves each corresponding subproblem \(F_{\lambda _k}\) iteratively. By taking advantage of the equivalently formulation of \(e_{\lambda _k} P_1({\mathbf {v}})\), i.e.,
we can reformulate \(F_{\lambda _k}\) as a DC problem, which can be solved by the \(\text {NPG}_\text {major}\) method. The \(\text {NPG}_\text {major}\) method solves the DC subproblem by combing the proximal gradient method with the nonmonotone line search technique, and terminates when the first-order optimality condition is satisfied. Note that, for the \(\text {NPG}_\text {major}\) method, we need to calculate the subgradient of \(D_{\lambda , P_1}({\mathbf {v}})\), which is proved equal to \(\frac{1}{\mu } \text {prox}_{\lambda _k,P_1}({\mathbf {v}})\). The proximity operator of \(\ell _p\) norm with \(p= 1/2\) (or \(p=2/3\)) has an analytic solution, which is provided in [46].
Rights and permissions
About this article
Cite this article
Wang, H., Zhang, F., Shi, Y. et al. Nonconvex and Nonsmooth Sparse Optimization via Adaptively Iterative Reweighted Methods. J Glob Optim 81, 717–748 (2021). https://doi.org/10.1007/s10898-021-01093-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-021-01093-0