Abstract
In this paper, we consider a non-convex problem which is the sum of \(\ell _0\)-norm and a convex smooth function under a box constraint. We propose one proximal iterative hard thresholding type method with an extrapolation step for acceleration and establish its global convergence results. In detail, the sequence generated by the proposed method globally converges to a local minimizer of the objective function. Finally, we conduct numerical experiments to show the proposed method’s effectiveness on comparison with some other efficient methods.
Similar content being viewed by others
References
Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka–Łojasiewicz inequality. Math. Oper. Res. 35(2), 438–457 (2008)
Attouch, H., Bolte, J., Svaiter, B.F.: 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 (2013)
Attouch, H., Peypouquet, J.: The rate of convergence of nesterov’s accelerated forward–backward method is actually faster than \(1/k^2\). SIAM J. Optim. 26(3), 1824–1834 (2016). https://doi.org/10.1137/15M1046095
Bao, C., Dong, B., Hou, L., Shen, Z., Zhang, X., Zhang, X.: Image restoration by minimizing zero norm of wavelet frame coefficients. Inverse Probl. 32(11), 115,004 (2016)
Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183–202 (2009)
Blumensath, T., Davies, M.E.: Iterative thresholding for sparse approximations. J. Fourier Anal. Appl. 14(5), 629–654 (2008)
Blumensath, T., Davies, M.E.: Iterative hard thresholding for compressed sensing. Appl. Comput. Harmon. Anal. 27(3), 265–274 (2009)
Bolte, J., Daniilidis, A., Lewis, A., Shiota, M.: Clarke subgradients of stratifiable functions. SIAM J. Optim. 18(2), 556–572 (2007)
Bolte, J., Daniilidis, A., Ley, O., Mazet, L., et al.: Characterizations of lojasiewicz inequalities: subgradient flows, talweg, convexity. Trans. Am. Math. Soc 362(6), 3319–3363 (2010)
Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1), 459–494 (2014)
Bot, R.I., Csetnek, E.R., László, S.C.: An inertial forwardcbackward algorithm for the minimization of the sum of two nonconvex functions. EURO J. Comput. Optim. 4(1), 3–25 (2016)
Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489–509 (2006)
Chan, R., Chan, T., Shen, L., Shen, Z.: Wavelet algorithms for high-resolution image reconstruction. SIAM J. Sci. Comput. 24, 1408–1432 (2003)
Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward–backward splitting. Multiscale Model. Simul. 4(4), 1168–1200 (2005)
Dong, B., Zhang, Y.: An efficient algorithm for \(l_0\) minimization in wavelet frame based image restoration. J. Sci. Comput. 54(2), 350–368 (2013)
Edmunds, B., Peng, Z., Yin, W.: TMAC: a toolbox of modern async-parallel, coordinate, splitting, and stochastic methods. CAM report 16–38, UCLA (2016)
Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348–1360 (2001)
Kurdyka, K., Parusinski, A.: \(w_f\)-stratification of subanalytic functions and the łojasiewicz inequality. Comptes Rendus Lacadémie Sci. Sér. Math. 318(2), 129–133 (1994)
Li, H., Lin, Z.: Accelerated proximal gradient methods for nonconvex programming. In Advances in Neural Information Processing Systems (NIPS), p. 28. (2015)
Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964–979 (1979)
Łojasiewicz, S.: Une propriété topologique des sous-ensembles analytiques réels. Les Équations Aux Dérivées Partielles 117, 87–89 (1963)
Lu, Z.: Iterative hard thresholding methods for \(l_0\) regularized convex cone programming. Math. Program. 147(1), 125–154 (2014)
Ochs, P., Chen, Y., Brox, T., Pock, T.: iPiano: inertial proximal algorithm for non-convex optimization. SIAM J. Imaging Sci. 7(2), 1388–1419 (2014)
Passty, G.B.: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space. J. Math. Anal. Appl. 72(2), 383–390 (1979)
Pock, T., Sabach, S.: Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems. SIAM J. Imaging Sci. 9(4), 1756–1787 (2016). https://doi.org/10.1137/16M1064064
Salzo, S., Villa, S.: Inexact and accelerated proximal point algorithms. J. Convex Anal. 19(4), 1167–1192 (2012)
Shen, Z., Toh, K.C., Yun, S.: An accelerated proximal gradient algorithm for frame-based image restoration via the balanced approach. SIAM J. Imaging Sci. 4(2), 573–596 (2011)
Xu, Y., Yin, W.: A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM J. Imaging Sci. 6(3), 1758–1789 (2013)
Zhang, X., Lu, Y., Chan, T.: A novel sparsity reconstruction method from poisson data for 3D bioluminescence tomography. J. Sci. Comput. 50(3), 519–535 (2012)
Zhang, X., Zhang, X.Q.: A note on the complexity of proximal iterative hard thresholding algorithm. J. Oper. Res. Soc. China 3(4), 459–473 (2015)
Zhang, Y., Dong, B., Lu, Z.: \(\ell _0\) minimization for wavelet frame based image restoration. Math. Comput. 82(282), 995–1015 (2013)
Acknowledgements
This work was partially supported by NSFC (No. 11771288), National key research and development program (No. 2017YFB0202902), the Young Top-notch Talent program of China, and 973 program (No. 2015CB856004).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhang, X., Zhang, X. A New Proximal Iterative Hard Thresholding Method with Extrapolation for \(\ell _0\) Minimization. J Sci Comput 79, 809–826 (2019). https://doi.org/10.1007/s10915-018-0874-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-018-0874-8