Skip to main content
Springer Nature Link
Log in

Nonconvex and Nonsmooth Sparse Optimization via Adaptively Iterative Reweighted Methods

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. 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)

    Article  MathSciNet  MATH  Google Scholar 

  2. 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)

    MATH  Google Scholar 

  3. 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)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bian, W., Chen, X.: Optimality and complexity for constrained optimization problems with nonconvex regularization. Math. Oper. Res. 42(4), 1063–1084 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bradley, P.S., Mangasarian, O.L., Street, W.N.: Feature selection via mathematical programming. INFORMS J. Comput. 10(2), 209–217 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  6. 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)

    Article  MathSciNet  MATH  Google Scholar 

  7. Candès, E.J., Wakin, M.B.: An introduction to compressive sampling. IEEE Signal Process. Mag. 25(2), 21–30 (2008)

    Article  Google Scholar 

  8. 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)

    Article  MathSciNet  MATH  Google Scholar 

  9. 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)

  10. 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)

    Google Scholar 

  11. 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)

    Article  MathSciNet  MATH  Google Scholar 

  12. Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348–1360 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  13. 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)

  14. Grant, M., Boyd, S., Ye, Y.: CVX: Matlab software for disciplined convex programming (2008). (Web page and software.) http://stanford.edu/~boyd/cvx (2015)

  15. Harrell, F.E.: Ordinal logistic regression. In: Regression modeling strategies, pp. 311–325. Springer (2015)

  16. Hastie, T., Tibshirani, R., Wainwright, M.: Statistical Learning with Sparsity: The Lasso and Generalizations. CRC Press, Boca Raton (2015)

    Book  MATH  Google Scholar 

  17. Holland, P.W., Welsch, R.E.: Robust regression using iteratively reweighted least-squares. Commun. Stat. Theory Methods 6(9), 813–827 (1977)

    Article  MATH  Google Scholar 

  18. 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)

    MathSciNet  Google Scholar 

  19. 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)

    Article  MathSciNet  MATH  Google Scholar 

  20. Kruger, A.Y.: \(\varepsilon \)-semidifferentials and \(\varepsilon \)-normal elements. Depon. VINITI 1331,(1981)

  21. Kruger, A.Y.: On fréchet subdifferentials. J. Math. Sci. 116(3), 3325–3358 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  22. 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)

    Article  MathSciNet  Google Scholar 

  23. 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)

  24. Ling, Q., Wen, Z., Yin, W.: Decentralized jointly sparse optimization by reweighted \(\ell _q\) minimization. IEEE Trans. Signal Process. 61(5), 1165–1170 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  25. 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)

    Article  Google Scholar 

  26. Lobo, M.S., Fazel, M., Boyd, S.: Portfolio optimization with linear and fixed transaction costs. Ann. Oper. Res. 152(1), 341–365 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  27. 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)

  28. Lu, Z.: Iterative reweighted minimization methods for \(\ell _p\) regularized unconstrained nonlinear programming. Math. Program. 147(1–2), 277–307 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  29. 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)

    Article  MathSciNet  MATH  Google Scholar 

  30. 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)

    Article  MathSciNet  MATH  Google Scholar 

  31. 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)

    Article  MathSciNet  MATH  Google Scholar 

  32. 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)

    Article  MathSciNet  MATH  Google Scholar 

  33. Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Siam, New Delhi (1970)

    MATH  Google Scholar 

  34. 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)

    Article  Google Scholar 

  35. Rockafellar, R.T., Wets, R.J.B.: Variational Analysis, vol. 317. Springer Science & Business Media, New York (2009)

    MATH  Google Scholar 

  36. 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)

    Article  Google Scholar 

  37. 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)

    Article  Google Scholar 

  38. Shi, Y., Zhang, J., Letaief, K.B.: Group sparse beamforming for green cloud-ran. IEEE Trans. Wirel. Commun. 13(5), 2809–2823 (2014)

    Article  Google Scholar 

  39. 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)

    Google Scholar 

  40. Wainwright, M.J.: Structured regularizers for high-dimensional problems: statistical and computational issues. Annu. Rev. Stat. Appl. 1, 233–253 (2014)

    Article  Google Scholar 

  41. Wang, H., Li, D.H., Zhang, X.J., Wu, L.: Optimality conditions for the constrained \( \ell _p \)-regularization. Optimization 64(10), 2183–2197 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  42. 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)

    MathSciNet  MATH  Google Scholar 

  43. Zhang, C.H.: Penalized linear unbiased selection. In: Department of Statistics and Bioinformatics. Rutgers University, New Jersey (2007)

    Google Scholar 

  44. 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)

    Article  MathSciNet  MATH  Google Scholar 

  45. 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)

    Article  MathSciNet  MATH  Google Scholar 

  46. 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)

    Article  Google Scholar 

  47. 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)

    Article  MathSciNet  MATH  Google Scholar 

  48. 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

    Google Scholar 

Download references

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

  1. School of Information Science and Technology, ShanghaiTech University, Shanghai, 201210, People’s Republic of China

    Hao Wang, Fan Zhang & Yuanming Shi

  2. Shenzhen Key Laboratory of Advanced Machine Learning and Applications, College of Mathematics and Statistics, Shenzhen University, Shenzhen, 518061, People’s Republic of China

    Yaohua Hu

  3. University of Chinese Academy of Sciences, Beijing, 100049, People’s Republic of China

    Fan Zhang

  4. Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai, 200050, People’s Republic of China

    Fan Zhang

Authors
  1. Hao Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fan Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yuanming Shi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yaohua Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hao Wang.

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

$$\begin{aligned} \varOmega := \left\{ {\mathbf {v}}: \sqrt{\sum \limits _{i\ne k}\Vert {\mathbf {h}}_k^\mathsf{{H}} {\mathbf {v}}_i \Vert _2^2 + \sigma _k^2}\le \frac{1}{\gamma _k}\mathfrak {R}({\mathbf {h}}_k^\mathsf{{H}} {\mathbf {v}}_k),\ \Vert {\tilde{{\mathbf {v}}}}_{l} \Vert _2\le \sqrt{P_l},\ l =1,\cdots ,L,\ k = 1,\cdots , K \right\} , \end{aligned}$$

and

$$\begin{aligned} P_1({\mathbf {v}}) := \sum _{l=1}^{L}\sqrt{\frac{\rho _l}{\eta _l}}\Vert \tilde{{\mathbf {v}}}_l\Vert _2^p\quad \text {and}\quad P_0({\mathbf {v}}) := \delta ({\mathbf {v}}|\varOmega ), \end{aligned}$$

we can reformulate problem (16) as

$$\begin{aligned} \min \limits _{{\mathbf {v}}}\quad F({\mathbf {v}}):= P_0({\mathbf {v}}) + P_1({\mathbf {v}}). \end{aligned}$$

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

$$\begin{aligned} \min \limits _{{\mathbf {v}}}\quad F_{\lambda _k}({\mathbf {v}}):= P_0({\mathbf {v}}) + e_{\lambda _k} P_1({\mathbf {v}}), \end{aligned}$$

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

$$\begin{aligned} e_{\lambda _k} P_1({\mathbf {v}}) = := \inf \limits _{{\mathbf {x}}}\{\frac{1}{2\lambda _k}\Vert {\mathbf {v}}-{\mathbf {y}}\Vert _2^2 + P_1({\mathbf {y}})\}. \end{aligned}$$

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.,

$$\begin{aligned} e_{\lambda _k} P_1({\mathbf {v}}) = \frac{1}{2\lambda }\Vert {\mathbf {v}}\Vert _2^2 - \underbrace{\sup \limits _{{\mathbf {y}}\in \text {dom}\ P_1}\{\frac{1}{\lambda }{\mathbf {v}}^T{\mathbf {y}} - \frac{1}{2\lambda }\Vert {\mathbf {y}}\Vert _2^2-P_1({\mathbf {y}})\}}_{D_{\lambda , P_1}({\mathbf {v}})}, \end{aligned}$$

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-021-01093-0

Keywords

Search

Navigation