×

Inexact half-quadratic optimization for linear inverse problems. (English) Zbl 1411.94010

Summary: We study the convergence of a generic half-quadratic algorithm for minimizing a wide class of \(C^{1}\) objectives that occur in inverse imaging problems; this algorithm amounts to solving a sequence of positive definite systems (the inner systems) and has the advantages of simplicity and versatility. Half-quadratic optimization has been meticulously studied, both theoretically and experimentally, but two difficulties remain: first, the practical solutions of the inner systems are approximate, which may hamper convergence; and second, convergence to a stationary point of the objective is not guaranteed if the set of such points contains a continuum. We present new results that do not suffer from these limitations and hence extend our work in [M. Robini and Y. Zhu, SIAM J. Imaging Sci. 8, No. 3, 1752–1797 (2015; Zbl 1326.49058)]. We consider the inexact process in which the inner systems are solved to a fixed arbitrary accuracy defined in terms of the energy norm of the error. We show that this process converges to a stationary point of the objective under minimal conditions ubiquitous in regularized reconstruction and restoration. Our main results are based on the assumption that the objective has the Kurdyka-Łojasiewicz property, for which we provide constructing rules using the concept of tameness from the theory of o-minimal structures. We also propose an implementation using a truncated conjugate gradient method that controls the accuracy at negligible additional cost. Experiments on three different inverse problems show that the resulting algorithm performs well in various nonconvex scenarios and converges to solutions accurate to full machine precision.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
49N45 Inverse problems in optimal control
54C60 Set-valued maps in general topology
65F22 Ill-posedness and regularization problems in numerical linear algebra
65K05 Numerical mathematical programming methods
65K10 Numerical optimization and variational techniques
90C26 Nonconvex programming, global optimization

Citations:

Zbl 1326.49058

Software:

mctoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.-F. Cai, R. Chan, and M. Nikolova, Two-phase approach for deblurring images corrupted by impulse plus Gaussian noise, Inverse Probl. Imaging, 2 (2008), pp. 187–204. · Zbl 1154.94306
[2] E. López-Rubio, Restoration of images corrupted by Gaussian and uniform impulsive noise, Pattern Recognit., 43 (2010), pp. 1835–1846. · Zbl 1191.68590
[3] Y. Xiao, T. Zeng, J. Yu, and M. Ng, Restoration of images corrupted by mixed Gaussian-impulse noise via \(l_1\)–\(l_0\) minimization, Pattern Recognit., 44 (2011), pp. 1708–1720. · Zbl 1218.68191
[4] B. Dong, H. Ji, J. Li, Z. Shen, and Y. Xu, Wavelet frame based blind image inpainting, Appl. Comput. Harmon. Anal., 32 (2012), pp. 268–279. · Zbl 1261.94006
[5] M. Yan, Restoration of images corrupted by impulse noise and mixed Gaussian impulse noise using blind inpainting, SIAM J. Imaging Sci., 6 (2013), pp. 1227–1245, . · Zbl 1281.65045
[6] J. Delon and A. Desolneux, A patch-based approach for removing impulse or mixed Gaussian-impulse noise, SIAM J. Imaging Sci., 6 (2013), pp. 1140–1174, . · Zbl 1278.62156
[7] L. Yue, H. Shen, Q. Yuan, and L. Zhang, A locally adaptive \(L_1\)–\(L_2\) norm for multi-frame super-resolution of images with mixed noise and outliers, Signal Process., 105 (2014), pp. 156–174.
[8] Y. Shen, B. Han, and E. Braverman, Removal of mixed Gaussian and impulse noise using directional tensor product complex tight framelets, J. Math. Imaging Vis., 54 (2016), pp. 64–77. · Zbl 1339.94012
[9] M. Bertero and P. Boccacci, Introduction to Inverse Problems in Imaging, CRC Press, 1998. · Zbl 0914.65060
[10] A. Ribes and F. Schmitt, Linear inverse problems in imaging, IEEE Signal Processing Mag., 25 (2008), pp. 84–99.
[11] M. Robini, Y. Zhu, and J. Luo, Edge-preserving reconstruction with contour-line smoothing and non-quadratic data-fidelity, Inverse Probl. Imaging, 7 (2013), pp. 1331–1366. · Zbl 1286.94026
[12] M. C. Robini and Y. Zhu, Generic half-quadratic optimization for image reconstruction, SIAM J. Imaging Sci., 8 (2015), pp. 1752–1797, . · Zbl 1326.49058
[13] S. Li, Markov Random Field Modeling in Computer Vision, Springer, 1995.
[14] R. He, W.-S. Zheng, T. Tan, and Z. Sun, Half-quadratic-based iterative minimization for robust sparse representation, IEEE Trans. Pattern Anal. Machine Intell., 36 (2014), pp. 261–275.
[15] P. Charbonnier, L. Blanc-Féraud, G. Aubert, and M. Barlaud, Deterministic edge-preserving regularization in computed imaging, IEEE Trans. Image Process., 6 (1997), pp. 298–311.
[16] A. Delaney and Y. Bresler, Globally convergent edge-preserving regularized reconstruction: An application to limited-angle tomography, IEEE Trans. Image Process., 7 (1998), pp. 204–221.
[17] J. Idier, Convex half-quadratic criteria and interacting auxiliary variables for image restoration, IEEE Trans. Image Process., 10 (2001), pp. 1001–1009. · Zbl 1036.68616
[18] M. Nikolova and M. K. Ng, Analysis of half-quadratic minimization methods for signal and image recovery, SIAM J. Sci. Comput., 27 (2005), pp. 937–966, . · Zbl 1141.49318
[19] M. Allain, J. Idier, and Y. Goussard, On global and local convergence of half-quadratic algorithms, IEEE Trans. Image Process., 15 (2006), pp. 1130–1142.
[20] P. Ochs, A. Dosovitskiy, T. Brox, and T. Pock, On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision, SIAM J. Imaging Sci., 8 (2015), pp. 331–372, . · Zbl 1326.65078
[21] R. Meyer, Sufficient conditions for the convergence of monotonic mathematical programming algorithms, J. Comput. System Sci., 12 (1976), pp. 108–121. · Zbl 0337.65037
[22] K. Kurdyka, On gradients of functions definable in o-minimal structures, Ann. Inst. Fourier, 48 (1998), pp. 769–783. · Zbl 0934.32009
[23] H. Attouch, J. Bolte, P. Redont, and A. Soubeyran, Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality, Math. Oper. Res., 35 (2010), pp. 438–457. · Zbl 1214.65036
[24] H. Attouch, J. Bolte, and B. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program. Ser. A, 137 (2013), pp. 91–129. · Zbl 1260.49048
[25] E. Chouzenoux, A. Jezierska, J.-C. Pesquet, and H. Talbot, A majorize-minimize subspace approach for \(ℓ_2\)-\(ℓ_0\) image regularization, SIAM J. Imaging Sci., 6 (2013), pp. 563–591, . · Zbl 1281.65030
[26] E. Chouzenoux, J.-C. Pesquet, and A. Repetti, Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function, J. Optim. Theory Appl., 162 (2014), pp. 107–132. · Zbl 1318.90058
[27] L. van den Dries and C. Miller, Geometric categories and o-minimal structures, Duke Math. J., 84 (1996), pp. 497–540. · Zbl 0889.03025
[28] L. van den Dries, Tame Topology and O-Minimal Structures, Cambridge University Press, 1998. · Zbl 0953.03045
[29] L. van den Dries, O-minimal structures and real analytic geometry, in Current Developments in Mathematics, International Press, Boston, 1998, pp. 105–152. · Zbl 0980.03043
[30] D. Hunter and K. Lange, A tutorial on MM algorithms, Amer. Statist., 58 (2004), pp. 30–37.
[31] T. Wu and K. Lange, The MM alternative to EM, Statist. Sci., 25 (2010), pp. 492–505. · Zbl 1329.62106
[32] M. Jacobson and J. Fessler, An expanded theoretical treatment of iteration-dependent majorize-minimize algorithms, IEEE Trans. Image Process., 16 (2007), pp. 2411–2422.
[33] J. Bolte, A. Daniilidis, and A. Lewis, The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17 (2007), pp. 1205–1223, . · Zbl 1129.26012
[34] J. Bochnak, M. Coste, and M.-F. Roy, Real Algebraic Geometry, Springer, 1998. · Zbl 0912.14023
[35] J. Bolte, A. Daniilidis, and A. Lewis, Tame functions are semismooth, Math. Program. Ser. B, 117 (2009), pp. 5–19. · Zbl 1158.49030
[36] H. Whitney, A function not constant on a connected set of critical points, Duke Math. J., 1 (1935), pp. 514–517. · JFM 61.1117.01
[37] L. van den Dries, A. Macintyre, and D. Marker, Logarithmic-exponential power series, J. Lond. Math. Soc., 56 (1997), pp. 417–434. · Zbl 0924.12007
[38] P. Speissegger, The Pfaffian closure on an o-minimal structure, J. Reine Angew. Math., 508 (1999), pp. 198–211. · Zbl 1067.14519
[39] P. Speissegger, Pfaffian sets and o-minimality, in Lecture Notes on O-Minimal Structures and Real Analytic Geometry, Springer, 2012, pp. 179–217. · Zbl 1266.14047
[40] G. Jones and P. Speissegger, Generating the Pfaffian closure with total Pfaffian functions, J. Logic Anal., 4 (2012). · Zbl 1298.14065
[41] L. van den Dries and P. Speissegger, The real field with convergent generalized power series, Trans. Amer. Math. Soc., 350 (1998), pp. 4377–4421. · Zbl 0905.03022
[42] L. van den Dries and P. Speissegger, The field of reals with multisummable series and the exponential function, Proc. Lond. Math. Soc., 81 (2000), pp. 513–565. · Zbl 1062.03029
[43] W. Hackbusch, Iterative Solution of Large Sparse Systems of Equations, Appl. Math. Sci. 95, Springer, 1994. · Zbl 0789.65017
[44] A. Björck, T. Elfving, and Z. Strakoš, Stability of conjugate gradient and Lanczos methods for linear least squares problems, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 720–736, . · Zbl 0924.65035
[45] R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, 1994, .
[46] N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002, . · Zbl 1011.65010
[47] Z. Strakoš and J. Liesen, On numerical stability in large scale linear algebraic computations, Z. Angew. Math. Mech., 85 (2005), pp. 307–325. · Zbl 1069.65030
[48] J. Rigal and J. Gaches, On the compatibility of a given solution with the data of a linear system, J. Assoc. Comput. Mach., 14 (1967), pp. 543–548. · Zbl 0183.17704
[49] Z. Strakoš and P. Tichý, Error estimation in preconditioned conjugate gradients, BIT, 45 (2005), pp. 789–817.
[50] M. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49 (1952), pp. 409–436. · Zbl 0048.09901
[51] G. Golub and G. Meurant, Matrices, Moments and Quadrature with Applications, Princeton University Press, 2010. · Zbl 1217.65056
[52] G. Meurant and P. Tichý, On computing quadrature-based bounds for the \(A\)-norm of the error in conjugate gradients, Numer. Algorithms, 62 (2013), pp. 163–191. · Zbl 1261.65034
[53] C. Labat and J. Idier, Convergence of Truncated Half-Quadratic and Newton Algorithms, with Application to Image Restoration, tech. report, IRCCyN, Nantes, 2007.
[54] Z. Strakoš and P. Tichý, On error estimation in the conjugate gradient method and why it works in finite precision computations, Electron. Trans. Numer. Anal., 13 (2002), pp. 56–80. · Zbl 1026.65027
[55] G. Meurant, The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations, SIAM, 2006, . · Zbl 1110.65029
[56] A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl., 113 (1989), pp. 7–63. · Zbl 0662.65032
[57] A. Greenbaum and Z. Strakoš, Predicting the behavior of finite precision Lanczos and conjugate gradient computations, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 121–137, . · Zbl 0755.65037
[58] Z. Wang, A. Bovik, H. Sheikh, and E. Simoncelli, Image quality assessment: From error visibility to structural similarity, IEEE Trans. Image Process., 13 (2004), pp. 600–612.
[59] T. Lei and W. Sewchand, Statistical approach to X-ray CT imaging and its applications in image analysis—Part I: Statistical analysis of X-ray CT imaging, IEEE Trans. Med. Imag., 11 (1992), pp. 53–61.
[60] M. Black and A. Rangarajan, On the unification of line processes, outlier rejection, and robust statistics with applications in early vision, Int. J. Comput. Vis., 19 (1996), pp. 57–91.
[61] J.-F. Cai, R. Chan, L. Shen, and Z. Shen, Convergence analysis of tight framelet approach for missing data recovery, Adv. Comput. Math., 31 (2009), pp. 87–113. · Zbl 1172.94309
[62] S. Ravishankar and Y. Bresler, Learning sparsifying transforms, IEEE Trans. Signal Process., 61 (2013), pp. 1072–1086. · Zbl 1393.94409
[63] S. Ravishankar and Y. Bresler, Learning doubly sparse transforms for images, IEEE Trans. Image Process., 22 (2013), pp. 4598–4612. · Zbl 1373.94344
[64] R. Acar and C. Vogel, Analysis of bounded variation penalty methods for ill-posed problems, Inverse Problems, 10 (1994), pp. 1217–1229. · Zbl 0809.35151
[65] P. Green, Bayesian reconstructions from emission tomography data using a modified EM algorithm, IEEE Trans. Med. Imag., 9 (1990), pp. 84–93.
[66] K. Lange, Convergence of EM image reconstruction algorithms with Gibbs priors, IEEE Trans. Med. Imag., 9 (1990), pp. 439–446.
[67] M. Black, G. Sapiro, D. Marimont, and D. Heeger, Robust anisotropic diffusion, IEEE Trans. Image Process., 7 (1998), pp. 421–432.
[68] W. Li and J. J. Swetits, The linear \(ℓ_1\) estimator and the Huber M-estimator, SIAM J. Optim., 8 (1998), pp. 457–475, . · Zbl 0914.90267
[69] T. Hebert and R. Leahy, A generalized EM algorithm for \(3\)-D Bayesian reconstruction from Poisson data using Gibbs priors, IEEE Trans. Med. Imag., 8 (1989), pp. 194–202.
[70] S. Geman and D. McClure, Bayesian image analysis: An application to single photon emission tomography, in Proc. Amer. Stat. Assoc., Stat. Comput. Section, Las Vegas, NV, 1985, pp. 12–18.
[71] J. Dennis and R. Welsch, Techniques for nonlinear least squares and robust regression, Commun. Stat. Simul. Comput., 7 (1978), pp. 345–359. · Zbl 0395.62046
[72] Y. Leclerc, Constructing stable descriptions for image partitioning, Int. J. Comput. Vis., 3 (1989), pp. 73–102.
[73] L. van den Dries, A generalization of the Tarski-Seidenberg theorem, and some nondefinability results, Bull. Amer. Math. Soc. (N.S.), 15 (1986), pp. 189–193. · Zbl 0612.03008
[74] L. van den Dries and C. Miller, On the real exponential field with restricted analytic functions, Israel J. Math., 85 (1994), pp. 19–56. · Zbl 0823.03017
[75] J.-P. Rolin, P. Speissegger, and A. Wilkie, Quasianalytic Denjoy-Carleman classes and o-minimality, J. Amer. Math. Soc., 16 (2003), pp. 751–777. · Zbl 1095.26018
[76] E. Bierstone and P. Milman, Semianalytic and subanalytic sets, Publ. Math. Inst. Hautes Études Sci., 67 (1988), pp. 5–42. · Zbl 0674.32002
[77] C. Miller, Expansions of the real field with power functions, Ann. Pure Appl. Logic, 68 (1994), pp. 79–94. · Zbl 0823.03018
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.