{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:52:29Z","timestamp":1759146749341,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,3,13]],"date-time":"2021-03-13T00:00:00Z","timestamp":1615593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,13]],"date-time":"2021-03-13T00:00:00Z","timestamp":1615593600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study a 1-dimensional discrete signal denoising problem that consists of minimizing a sum of separable convex fidelity terms and convex regularization terms, the latter penalize the differences of adjacent signal values. This problem generalizes the total variation regularization problem. We provide here a unified approach to solve the problem for general convex fidelity and regularization functions that is based on the Karush\u2013Kuhn\u2013Tucker optimality conditions. This approach is shown here to lead to a fast algorithm for the problem with general convex fidelity and regularization functions, and a faster algorithm if, in addition, the fidelity functions are differentiable and the regularization functions are strictly convex. Both algorithms achieve the best theoretical worst case complexity over existing algorithms for the classes of objective functions studied here. Also in practice, our C++ implementation of the method is considerably faster than popular C++ nonlinear optimization solvers for the problem.<\/jats:p>","DOI":"10.1007\/s10107-021-01633-2","type":"journal-article","created":{"date-parts":[[2021,3,13]],"date-time":"2021-03-13T15:02:46Z","timestamp":1615647766000},"page":"415-442","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A unified approach for a 1D generalized total variation problem"],"prefix":"10.1007","volume":"194","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5137-7199","authenticated-orcid":false,"given":"Cheng","family":"Lu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2498-0512","authenticated-orcid":false,"given":"Dorit S.","family":"Hochbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,13]]},"reference":[{"issue":"7","key":"1633_CR1","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1287\/mnsc.49.7.950.16384","volume":"49","author":"RK Ahuja","year":"2003","unstructured":"Ahuja, R.K., Hochbaum, D.S., Orlin, J.B.: Solving the convex cost integer dual network flow problem. Manag. Sci. 49(7), 950\u2013964 (2003)","journal-title":"Manag. Sci."},{"issue":"1","key":"1633_CR2","first-page":"2232","volume":"19","author":"\u00c1 Barbero","year":"2018","unstructured":"Barbero, \u00c1., Sra, S.: Modular proximal optimization for multidimensional total-variation regularization. J. Mach. Learn. Res. 19(1), 2232\u20132313 (2018)","journal-title":"J. Mach. Learn. Res."},{"key":"1633_CR3","volume-title":"Statistical Inference Under Order Restrictions: The Theory and Application of Isotonic Regression","author":"RE Barlow","year":"1972","unstructured":"Barlow, R.E., Bartholomew, D.J., Bremner, J.M., Brunk, H.D.: Statistical Inference Under Order Restrictions: The Theory and Application of Isotonic Regression. Wiley, New York (1972)"},{"issue":"11","key":"1633_CR4","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1109\/LSP.2013.2278339","volume":"20","author":"L Condat","year":"2013","unstructured":"Condat, L.: A direct algorithm for 1-D total variation denoising. IEEE Signal Process. Lett. 20(11), 1054\u20131057 (2013)","journal-title":"IEEE Signal Process. Lett."},{"key":"1633_CR5","volume-title":"Elementary Numerical Analysis","author":"SD Conte","year":"1972","unstructured":"Conte, S.D., de Boor, C.: Elementary Numerical Analysis. McGraw-Hill, New York (1972)"},{"issue":"1","key":"1633_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/aos\/996986501","volume":"29","author":"PL Davies","year":"2001","unstructured":"Davies, P.L., Kovac, A.: Local extremes, runs, strings and multiresolution. Ann. Stat. 29(1), 1\u201365 (2001)","journal-title":"Ann. Stat."},{"key":"1633_CR7","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1214\/08-EJS216","volume":"3","author":"L D\u00fcmbgen","year":"2009","unstructured":"D\u00fcmbgen, L., Kovac, A.: Extensions of smoothing via taut strings. Electron. J. Stat. 3, 41\u201375 (2009)","journal-title":"Electron. J. Stat."},{"issue":"1","key":"1633_CR8","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s10851-006-9796-4","volume":"27","author":"M Grasmair","year":"2007","unstructured":"Grasmair, M.: The equivalence of the taut string algorithm and BV-regularization. J. Math. Imag. Vis. 27(1), 59\u201366 (2007)","journal-title":"J. Math. Imag. Vis."},{"issue":"4","key":"1633_CR9","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1145\/502090.502093","volume":"48","author":"DS Hochbaum","year":"2001","unstructured":"Hochbaum, D.S.: An efficient algorithm for image segmentation, Markov random fields and related problems. J. ACM 48(4), 686\u2013701 (2001)","journal-title":"J. ACM"},{"issue":"1","key":"1633_CR10","doi-asserted-by":"publisher","first-page":"169","DOI":"10.4208\/nmtma.2013.mssvm09","volume":"6","author":"DS Hochbaum","year":"2013","unstructured":"Hochbaum, D.S.: Multi-label Markov random fields as an efficient and effective tool for image segmentation, total variations and regularization. Numer. Math. Theory Methods Appl. 6(1), 169\u2013198 (2013)","journal-title":"Numer. Math. Theory Methods Appl."},{"issue":"4","key":"1633_CR11","doi-asserted-by":"publisher","first-page":"2563","DOI":"10.1137\/15M1024081","volume":"27","author":"DS Hochbaum","year":"2017","unstructured":"Hochbaum, D.S., Lu, C.: A faster algorithm solving a generalization of isotonic median regression and a class of fused lasso problems. SIAM J. Optim. 27(4), 2563\u20132596 (2017)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"1633_CR12","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1145\/96559.96597","volume":"37","author":"DS Hochbaum","year":"1990","unstructured":"Hochbaum, D.S., Shanthikumar, J.G.: Nonlinear separable optimization is not much harder than linear optimization. J. ACM 37(4), 843\u2013862 (1990)","journal-title":"J. ACM"},{"issue":"1","key":"1633_CR13","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1214\/aoms\/1177703732","volume":"35","author":"P Huber","year":"1964","unstructured":"Huber, P.: Robust estimation of a location parameter. Ann. Math. Stat. 35(1), 73\u2013101 (1964)","journal-title":"Ann. Math. Stat."},{"issue":"2","key":"1633_CR14","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1080\/10618600.2012.681238","volume":"22","author":"NA Johnson","year":"2013","unstructured":"Johnson, N.A.: A dynamic programming algorithm for the fused lasso and $$L_0$$-segmentation. J. Comput. Graph. Stat. 22(2), 246\u2013260 (2013)","journal-title":"J. Comput. Graph. Stat."},{"issue":"2","key":"1633_CR15","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1137\/070690274","volume":"51","author":"S-J Kim","year":"2009","unstructured":"Kim, S.-J., Koh, K., Boyd, S., Gorinevsky, D.: $$\\ell _1$$ trend filtering. SIAM Rev. 51(2), 339\u2013360 (2009)","journal-title":"SIAM Rev."},{"issue":"2","key":"1633_CR16","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1137\/15M1010257","volume":"9","author":"V Kolmogorov","year":"2016","unstructured":"Kolmogorov, V., Pock, T., Rolinek, M.: Total variation on a tree. SIAM J. Imag. Sci. 9(2), 605\u2013636 (2016)","journal-title":"SIAM J. Imag. Sci."},{"issue":"2135","key":"1633_CR17","first-page":"3088","volume":"467","author":"MA Little","year":"2011","unstructured":"Little, M.A., Jones, N.S.: Generalized methods and solvers for noise removal from piecewise constant signals I Background theory. Proc. R. Soc. A Math. Phys. Eng. Sci. 467(2135), 3088\u20133114 (2011)","journal-title":"Proc. R. Soc. A Math. Phys. Eng. Sci."},{"issue":"1","key":"1633_CR18","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1214\/aos\/1034276635","volume":"25","author":"E Mammen","year":"1997","unstructured":"Mammen, E., van de Geer, S.: Locally adaptive regression splines. Ann. Stat. 25(1), 387\u2013413 (1997)","journal-title":"Ann. Stat."},{"issue":"1\u20134","key":"1633_CR19","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0167-2789(92)90242-F","volume":"60","author":"LI Rudin","year":"1992","unstructured":"Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60(1\u20134), 259\u2013268 (1992)","journal-title":"Physica D"},{"issue":"1","key":"1633_CR20","doi-asserted-by":"publisher","first-page":"A614","DOI":"10.1137\/15M101796X","volume":"38","author":"M Storath","year":"2016","unstructured":"Storath, M., Weinmann, A., Unser, M.: Exact algorithms for $$L^1$$-TV regularization of real-valued or circle-valued signals. SIAM J. Sci. Comput. 38(1), A614\u2013A630 (2016)","journal-title":"SIAM J. Sci. Comput."},{"issue":"4","key":"1633_CR21","doi-asserted-by":"publisher","first-page":"2226","DOI":"10.1137\/130951075","volume":"7","author":"A Weinmann","year":"2014","unstructured":"Weinmann, A., Demaret, L., Storath, M.: Total variation regularization for manifold-valued data. SIAM J. Imag. Sci. 7(4), 2226\u20132257 (2014)","journal-title":"SIAM J. Imag. Sci."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01633-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01633-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01633-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T19:09:38Z","timestamp":1656356978000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01633-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,13]]},"references-count":21,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["1633"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01633-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2021,3,13]]},"assertion":[{"value":"18 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}