{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:37:47Z","timestamp":1787323067111,"version":"build-2736575974"},"reference-count":77,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"Chinese Basic Research Program","award":["61671049"],"award-info":[{"award-number":["61671049"]}]},{"name":"Chinese Key R&D Program","award":["2017FB1400101"],"award-info":[{"award-number":["2017FB1400101"]}]},{"name":"Cai Yuanpei Program","award":["36702XD"],"award-info":[{"award-number":["36702XD"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Imaging Sci."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>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 (2015), pp. 1752--1797]. 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--\u0141ojasiewicz 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.<\/jats:p>","DOI":"10.1137\/17m114635x","type":"journal-article","created":{"date-parts":[[2018,5,1]],"date-time":"2018-05-01T12:46:58Z","timestamp":1525178818000},"page":"1078-1133","source":"Crossref","is-referenced-by-count":4,"title":["Inexact Half-Quadratic Optimization for Linear Inverse Problems"],"prefix":"10.1137","volume":"11","author":[{"given":"Marc C.","family":"Robini","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Feng","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuemin","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,5,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.3934\/ipi.2008.2.187"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2009.11.017"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2011.02.002"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2011.06.001"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/12087178X"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/120885000"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.sigpro.2014.04.031"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-015-0589-5"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"M. Bertero and P. Boccacci,\n                      Introduction to Inverse Problems in Imaging\n                      , CRC Press, 1998.","DOI":"10.1887\/0750304359"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2008.923099"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.3934\/ipi.2013.7.1331"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/140987845"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"S. Li,\n                      Markov Random Field Modeling in Computer Vision\n                      , Springer, 1995.","DOI":"10.1007\/978-4-431-66933-3"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.102"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/83.551699"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/83.660997"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1109\/83.931094"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/030600862"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2005.864173"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/140971518"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80021-9"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.5802\/aif.1638"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0449"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0484-9"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/11085997X"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-013-0465-7"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-96-08416-1"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"L. van den Dries,\n                      Tame Topology and O-Minimal Structures\n                      , Cambridge University Press, 1998.","DOI":"10.1017\/CBO9780511525919"},{"key":"atypb29","first-page":"105","author":"L","year":"1998","journal-title":"Boston"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1198\/0003130042836"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1214\/08-STS264"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2007.904387"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/050644641"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"J. Bochnak, M. Coste, and M.F. Roy,\n                      Real Algebraic Geometry\n                      , Springer, 1998.","DOI":"10.1007\/978-3-662-03718-8"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0166-9"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-35-00138-7"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1112\/S0024610797005437"},{"key":"atypb38","first-page":"198","volume":"508","author":"Speissegger P.","year":"1999","journal-title":"J. Reine Angew. Math."},{"key":"atypb39","first-page":"179","author":"Speissegger P.","year":"2012","journal-title":"Springer"},{"key":"atypb40","first-page":"4","author":"Jones G.","year":"2012","journal-title":"J. Logic Anal."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-98-02105-9"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1112\/S0024611500012648"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"W. Hackbusch,\n                      Iterative Solution of Large Sparse Systems of Equations\n                      , Appl. Math. Sci. 95, Springer, 1994.","DOI":"10.1007\/978-1-4612-4288-8"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1137\/S089547989631202X"},{"key":"atypb45","doi-asserted-by":"crossref","unstructured":"R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. van der Vorst,\n                      Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods\n                      , SIAM, 1994,https:\/\/doi.org\/10.1137\/1.9781611971538.","DOI":"10.1137\/1.9781611971538"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"N. J. Higham,\n                      Accuracy and Stability of Numerical Algorithms\n                      , 2nd ed., SIAM, 2002,https:\/\/doi.org\/10.1137\/1.9780898718027.","DOI":"10.1137\/1.9780898718027"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1002\/zamm.200410185"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1145\/321406.321416"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-005-0032-1"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"atypb51","doi-asserted-by":"crossref","unstructured":"G. Golub and G. Meurant,\n                      Matrices, Moments and Quadrature with Applications\n                      , Princeton University Press, 2010.","DOI":"10.1515\/9781400833887"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-012-9591-9"},{"key":"atypb53","unstructured":"C. Labat and J. Idier,\n                      Convergence of Truncated Half-Quadratic and Newton Algorithms, with Application to Image Restoration\n                      , tech. report, IRCCyN, Nantes, 2007."},{"key":"atypb54","first-page":"56","volume":"13","author":"Strakos\u030c Z.","year":"2002","journal-title":"Electron. Trans. Numer. Anal."},{"key":"atypb55","doi-asserted-by":"crossref","unstructured":"G. Meurant,\n                      The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations\n                      , SIAM, 2006,https:\/\/doi.org\/10.1137\/1.9780898718140.","DOI":"10.1137\/1.9780898718140"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(89)90285-1"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1137\/0613011"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2003.819861"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1109\/42.126910"},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1007\/BF00131148"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1007\/s10444-008-9084-5"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2012.2226449"},{"key":"atypb63","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2013.2274384"},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1088\/0266-5611\/10\/6\/003"},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1109\/42.52985"},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.1109\/42.61759"},{"key":"atypb67","doi-asserted-by":"publisher","DOI":"10.1109\/83.661192"},{"key":"atypb68","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623495293160"},{"key":"atypb69","doi-asserted-by":"publisher","DOI":"10.1109\/42.24868"},{"key":"atypb70","first-page":"12","author":"Geman S.","year":"1985","journal-title":"NV"},{"key":"atypb71","doi-asserted-by":"publisher","DOI":"10.1080\/03610917808812083"},{"key":"atypb72","doi-asserted-by":"publisher","DOI":"10.1007\/BF00054839"},{"key":"atypb73","first-page":"189","volume":"15","author":"L","year":"1986","journal-title":"S.)"},{"key":"atypb74","doi-asserted-by":"publisher","DOI":"10.1007\/BF02758635"},{"key":"atypb75","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-03-00427-2"},{"key":"atypb76","doi-asserted-by":"publisher","DOI":"10.1007\/BF02699126"},{"key":"atypb77","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)90048-5"}],"container-title":["SIAM Journal on Imaging Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M114635X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:40:03Z","timestamp":1787319603000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M114635X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":77,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M114635X"],"URL":"https:\/\/doi.org\/10.1137\/17m114635x","relation":{},"ISSN":["1936-4954"],"issn-type":[{"value":"1936-4954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}