Geodesic
Non-convex Optimization via Strongly Convex Majorization-minimization
Canadian mathematical bulletin, Tome 63 (2020) no. 4, pp. 726-737

Voir la notice de l'article provenant de la source Cambridge University Press

In this paper, we introduce a class of nonsmooth nonconvex optimization problems, and we propose to use a local iterative minimization-majorization (MM) algorithm to find an optimal solution for the optimization problem. The cost functions in our optimization problems are an extension of convex functions with MC separable penalty, which were previously introduced by Ivan Selesnick. These functions are not convex; therefore, convex optimization methods cannot be applied here to prove the existence of optimal minimum point for these functions. For our purpose, we use convex analysis tools to first construct a class of convex majorizers, which approximate the value of non-convex cost function locally, then use the MM algorithm to prove the existence of local minimum. The convergence of the algorithm is guaranteed when the iterative points $x^{(k)}$ are obtained in a ball centred at $x^{(k-1)}$ with small radius. We prove that the algorithm converges to a stationary point (local minimum) of cost function when the surregators are strongly convex.
DOI : 10.4153/S0008439519000730
Mots-clés : Cost function, local majorizer and minimizer, surregator, Moreau envelope, infimal convolution, convex function, stationary point 
Mayeli, Azita. Non-convex Optimization via Strongly Convex Majorization-minimization. Canadian mathematical bulletin, Tome 63 (2020) no. 4, pp. 726-737. doi: 10.4153/S0008439519000730
@article{10_4153_S0008439519000730,
     author = {Mayeli, Azita},
     title = {Non-convex {Optimization} via {Strongly} {Convex} {Majorization-minimization}},
     journal = {Canadian mathematical bulletin},
     pages = {726--737},
     year = {2020},
     volume = {63},
     number = {4},
     doi = {10.4153/S0008439519000730},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/S0008439519000730/}
}
TY  - JOUR
AU  - Mayeli, Azita
TI  - Non-convex Optimization via Strongly Convex Majorization-minimization
JO  - Canadian mathematical bulletin
PY  - 2020
SP  - 726
EP  - 737
VL  - 63
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/S0008439519000730/
DO  - 10.4153/S0008439519000730
ID  - 10_4153_S0008439519000730
ER  - 
%0 Journal Article
%A Mayeli, Azita
%T Non-convex Optimization via Strongly Convex Majorization-minimization
%J Canadian mathematical bulletin
%D 2020
%P 726-737
%V 63
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/S0008439519000730/
%R 10.4153/S0008439519000730
%F 10_4153_S0008439519000730

[1] R. G. Baraniuk, E. Candes, M. Elad, and Y. Ma, eds., Special issue on applications of sparse representation and compressive sensing. Proc. IEEE 98(June 2010), 6. Google Scholar | DOI

[2] Bauschke, H. H. and Combettes, P. L., Convex analysis and monotone operator theory in Hilbert spaces. In: CMS books in mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York, 2011. https://doi.org/10.1007/978-1-4419-9467-7 Google Scholar

[3] O’Brien, S., Sinclair, A. N., and Kramer, S. M., Recovery of a sparse spike time series by L 1 norm deconvolution. IEEE Trans. Signal Process. 42(December 1994), 12, 3353–3365. Google Scholar | DOI

[4] Bruckstein, A., Donoho, D., and Elad, M., From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51(2009), 34–81. https://doi.org/10.1137/060657704 Google Scholar | DOI

[5] Candes, E. J., Wakin, M. B., and Boyd, S., Enhancing sparsity by reweighted ℓ1 minimization. J. Fourier Anal. Appl. 14(2008), 877–905. https://doi.org/10.1007/s00041-008-9045-x Google Scholar | DOI

[6] Chartrand, R., Sidky, E.Y., and Pan, X., Nonconvex compressive sensing for X-ray CT: an algorithm comparison. In: 2013 Asilomar conference on signals, systems and computers. IEEE, 2013, pp. 665–669. Google Scholar | DOI

[7] Chen, S. S., Donoho, D. L., and Saunders, M. A., Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1999), 33–61. https://doi.org/10.1137/S1064827596304010 Google Scholar | DOI

[8] Claerbout, J. F. and Muir, F., Robust modeling of erratic data. Geophysics 38(1973), 826–844. Google Scholar | DOI

[9] Daubechies, I., Devore, R., Fornasier, M., and Gunturk, C., Iteratively reweighted least squares minimization for sparse recovery. Comm. Pure Appl. Math. 63(2010), 1–38. https://doi.org/10.1002/cpa.20303 Google Scholar | DOI

[10] Figueiredo, M., Bioucas-Dias, J., and Nowak, R., Majorization-minimization algorithms for wavelet-based image restoration. IEEE Trans. Image Process. 16(2007), 2980–2991. https://doi.org/10.1109/TIP.2007.909318 Google Scholar PubMed | DOI

[11] Gasso, G., Rakotomamonjy, A., and Canu., S., Recovering sparse signals with a certain family of nonconvex penalties and DC programming. IEEE Trans. Signal Process. 57(2009), 4686–4698. https://doi.org/10.1109/TSP.2009.2026004 Google Scholar | DOI

[12] Gholami, A. and Hosseini, S. M., A general framework for sparsity-based denoising and inversion. IEEE Trans. Signal Process. 59(2011), 11, 5202–5211. https://doi.org/10.1109/TSP.2011.2164074 Google Scholar | DOI

[13] Hastie, T., Tibshirani, R., and Friedman, J. H., The elements of statistical learning. In: Data mining, inference, and prediction, 2nd ed., Springer Series in Statistics, Springer, New York, 2009. https://doi.org/10.1007/978-0-387-84858-7 Google Scholar

[14] Lange, K., Chi, E. C., and Zhou, H., A brief survey of modern optimization for statisticians. Int. Stat. Rev. 82(2014), 46–70. https://doi.org/10.1111/insr.12022 Google Scholar PubMed | DOI

[15] Lang, K., Optimization, 2nd ed., Springer Texts in Statistics, 95, Springer, New York, 2013. https://doi.org/10.1007/978-1-4614-5838-8 Google Scholar | DOI

[16] Lanza, A., Morigi, S., Selesnick, I., and Sgallari, F., Nonconvex nonsmooth optimization via convex-nonconvex majorization-minimization. Numer. Math. 136(2017), 343–381. https://doi.org/10.1007/s00211-016-0842-x Google Scholar | DOI

[17] Malioutov, D. and Aravkin, A., Iterative log thresholding. In: 2014 IEEE International conference on acoustics, speech and signal processing (ICASSP). IEEE, 2014, pp. 7198–7202. Google Scholar | DOI

[18] Mairal, J., Optimization with first-order surrogate functions. In: ICML 2013-International conference on machine learning, June 2013, JMLR proceedings, Atlanta, USA. ICML, 2013, pp. 783–791. Google Scholar

[19] Selesnick, I., Sparse regularization via convex analysis. IEEE Trans. Signal Process. 65(2017), 4481–4494. https://doi.org/10.1109/TSP.2017.2711501 Google Scholar | DOI

[20] Selesnick, I., Total variation denoising via the Moreau envelope. IEEE Signal Processing Letters 24(2017), 216–220. Google Scholar | DOI

[21] Starck, J. L., Starck, J.-L., Murtagh, F., and Fadili, J., Sparse image and signal processing: Wavelets and related geometric multiscale analysis. Cambridge University Press, New York, 2015. https://doi.org/10.1017/CBO9781316104514 Google Scholar | DOI

[22] Taylor, H. L., Banks, S. C., and Mccoy, J. F., Deconvolution with the l1 norm. Geophysics 44(1979), 1, 39–52.10.1190/1.1440921 Google Scholar | DOI

[23] Tibshirani, R., Regression shrinkage and selection via the lasso. Technical report, University of Toronto, 1994. Google Scholar

[24] Xu, Z., Chang, X., Xu, F., and Zhang., H., L regularization: A thresholding representation theory and a fast solver. IEEE T. Neur. Net. Learn. 23(2012), 1013–1027. Google Scholar

[25] Yin, P., Lou, Y., He, Q., and Xin, J., Minimization of ℓ for compressed sensing. SIAM J. Sci. Comput. 37(2015), A536–A563. https://doi.org/10.1137/140952363 Google Scholar | DOI

[26] Zeng, J., Lin, S., Wang, Y., and Xu, Z., L regularization: Convergence of iterative half thresholding algorithm. IEEE Trans. Signal Process. 62(2014), 2317–2329. https://doi.org/10.1109/TSP.2014.2309076 Google Scholar | DOI

Cité par Sources :