zbMATH — the first resource for mathematics

The proximal alternating iterative hard thresholding method for \(l_0\) minimization, with complexity \(\mathcal{O}(1/\sqrt{k})\). (English) Zbl 1354.49071
Summary: Since digital images are usually sparse in the wavelet frame domain, some nonconvex minimization models based on wavelet frame have been proposed and sparse approximations have been widely used in image restoration in recent years. Among them, the proximal alternating iterative hard thresholding method is proposed in this paper to solve the nonconvex model based on wavelet frame. Through combining the proposed algorithm with the iterative hard thresholding algorithm which is well studied in compressed sensing theory, this paper proves that the complexity of the proposed method is \(\mathcal{O}(1/\sqrt{k})\). On the other hand, a more general nonconvex-nonsmooth model is adopted and the pseudo proximal alternating linearized minimization method is developed to solve the above problem. With the Kurdyka-Łojasiewicz (KL) property, it is proved that the sequence generated by the proposed algorithm converges to some critical points of the corresponding model. Finally, the proposed method is applied to restore the blurred noisy gray images. As the numerical results reveal, the performance of the proposed method is comparable or better than some well-known convex image restoration methods.

49M30 Other numerical methods in calculus of variations (MSC2010)
42C40 Nontrigonometric harmonic analysis involving wavelets and other special systems
42C15 General harmonic expansions, frames
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
68U10 Computing methodologies for image processing
Full Text: DOI
[1] C. Bao, B. Dong, L. Hou, Z. Shen, X. Zhang, X. Zhang, Extrapolated proximal iterative hard thresholding methods for wavelet frame based image restoration, manuscript, 2015.
[2] Bao, C.; Ji, H.; Shen, Z., Convergence analysis for iterative data-driven tight frame construction scheme, Appl. Comput. Harmon. Anal., 38, 3, 510-523, (2015) · Zbl 1361.94006
[3] Danielyan, A.; Katkovnik, V.; Egiazarian, K., BM3D frames and variational image deblurring, IEEE Trans. Image Process., 21, 4, 1715-1728, (2012) · Zbl 1373.94096
[4] J. Portilla, Image restoration through \(l_0\) analysis-based sparse optimization in tight frames, in: 16th IEEE International Conference on Image Processing, 2009.
[5] Zhang, Y.; Dong, B.; Lu, Z., \(l_0\) minimization of wavelet frame based image restoration, Math. Comp., 82, 282, 995-1015, (2013) · Zbl 1277.80022
[6] Lu, Z., Iterative hard thresholding methods for \(l_0\) regularized convex cone programming, Math. Program., 147, 1-2, 125-154, (2014) · Zbl 1308.65094
[7] Bolte, J.; Sabach, S.; Teboulle, M., Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146, 1-2, 459-494, (2014) · Zbl 1297.90125
[8] Rockafellar, R. T.; Wets, R. J.B., Variational analysis, (2009), Springer Science & Business Media
[9] Łojasiewicz, S., Une propriété topologique des sous ensembles analytiques réels, (Les Équations aux Dérivées Partielles, (1963), Éditions du centre National de la Recherche Scientifique Paris), 87-89
[10] Kurdyka, K., On gradients of functions definable in o-minimal structures, Ann. Inst. Fourier, 48, 3, 769-783, (1998) · Zbl 0934.32009
[11] Bolte, J.; Daniilidis, A.; Lewis, A., The łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17, 4, 1205-1223, (2007) · Zbl 1129.26012
[12] Bolte, J.; Daniilidis, A.; Ley, O.; Mazet, L., Characterizations of łojasiewicz inequalities: subgradient flows, talweg, convexity, Trans. Amer. Math. Soc., 362, 6, 3319-3363, (2010) · Zbl 1202.26026
[13] Attouch, H.; Bolte, J., On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., 116, 1-2, 5-16, (2009) · Zbl 1165.90018
[14] 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, (2010) · Zbl 1214.65036
[15] Xu, Y.; Yin, W., A block coordinate descent method for multi-convex optimization with applications to nonnegative tensor factorization and completion, SIAM J. Imag. Sci., 6, 3, 1758-1789, (2012) · Zbl 1280.49042
[16] Golub, G. H.; Van Loan, C. F., Matrix computations, (2012), JHU Press
[17] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imag. Sci., 2, 1, 183-202, (2009) · Zbl 1175.94009
[18] Ron, A.; Shen, Z., Affine systems in \(L_2(\mathbb{R}^d)\): the analysis of the analysis operator, J. Funct. Anal., 148, 2, 408-447, (1997) · Zbl 0891.42018
[19] Cai, J. F.; Osher, S.; Shen, Z., Split Bregman methods and frame based image restoration, Multiscale Model. Simul., 8, 2, 337-369, (2009) · Zbl 1189.94014
[20] Lu, Z.; Zhang, Y., Sparse approximation via penalty decomposition methods, SIAM J. Optim., 23, 4, 2448-2478, (2013) · Zbl 1295.90056
[21] Blumensath, T.; Davies, M. E., Iterative thresholding for sparse approximations, J. Fourier Anal. Appl., 14, 5-6, 629-654, (2008) · Zbl 1175.94060
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.