# American Institute of Mathematical Sciences

May  2015, 9(2): 511-550. doi: 10.3934/ipi.2015.9.511

## A study of the one dimensional total generalised variation regularisation problem

 1 Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Wilberforce Road, CB3 0WA, Cambridge, United Kingdom 2 Institute for Mathematics and Scientific Computing, University of Graz, Heinrichstrasse 36, A-8010, Graz, Austria

Received  October 2013 Revised  October 2014 Published  March 2015

In this paper we study the one dimensional second order total generalised variation regularisation (TGV) problem with $L^{2}$ data fitting term. We examine the properties of this model and we calculate exact solutions using simple piecewise affine functions as data terms. We investigate how these solutions behave with respect to the TGV parameters and we verify our results using numerical experiments.
Citation: Konstantinos Papafitsoros, Kristian Bredies. A study of the one dimensional total generalised variation regularisation problem. Inverse Problems and Imaging, 2015, 9 (2) : 511-550. doi: 10.3934/ipi.2015.9.511
##### References:
 [1] L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems, Oxford University Press, USA, 2000. [2] H. Attouch and H. Brezis, Duality for the sum of convex functions in general Banach spaces, North-Holland Mathematical Library, 34 (1986), 125-133. doi: 10.1016/S0924-6509(09)70252-1. [3] P. Belhumeur, A binocular stereo algorithm for reconstructing sloping, creased, and broken surfaces in the presence of half-occlusion, in Proceedings of the Fourth International Conference on Computer Vision, 1993, 431-438. doi: 10.1109/ICCV.1993.378184. [4] M. Benning, Singular Regularization of Inverse Problems, Bregman Distances and Applications to Variational Frameworks with Singular Regularization Energies, Ph.D thesis, University of Münster, 2011. [5] M. Benning, C. Brune, M. Burger and J. Müller, Higher-order TV methods - Enhancement via Bregman iteration, Journal of Scientific Computing, 54 (2013), 269-310. doi: 10.1007/s10915-012-9650-3. [6] M. Benning and M. Burger, Ground states and singular vectors of convex variational regularization methods, Methods and Applications of Analysis, 20 (2013), 295-334. doi: 10.4310/MAA.2013.v20.n4.a1. [7] K. Bredies, Recovering piecewise smooth multichannel images by minimization of convex functionals with total generalized variation penalty, in Efficient Algorithms for Global Optimization Methods in Computer Vision, Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2014, 44-77. doi: 10.1007/978-3-642-54774-4_3. [8] K. Bredies and M. Holler, Artifact-free decompression and zooming of JPEG compressed images with total generalized variation, in Computer Vision, Imaging and Computer Graphics - Theory and Application, Communications in Computer and Information Science, Springer Berlin Heidelberg, 2013, 242-258. doi: 10.1007/978-3-642-38241-3_16. [9] K. Bredies, K. Kunisch and T. Pock, Total generalized variation, SIAM Journal on Imaging Sciences, 3 (2010), 492-526. doi: 10.1137/090769521. [10] K. Bredies, K. Kunisch and T. Valkonen, Properties of $L^1$-$TGV^{2}$: The one-dimensional case, Journal of Mathematical Analysis and Applications, 398 (2013), 438-454. doi: 10.1016/j.jmaa.2012.08.053. [11] K. Bredies and T. Valkonen, Inverse problems with second-order total generalized variation constraints, in Proceedings of SampTA 2011 - 9th International Conference on Sampling Theory and Applications, Singapore, 2011. [12] V. Caselles, A. Chambolle and M. Novaga, The discontinuity set of solutions of the {TV} denoising problem and some extensions, Multiscale Modeling & Simulation, 6 (2007), 879-894. doi: 10.1137/070683003. [13] A. Chambolle and P. Lions, Image recovery via total variation minimization and related problems, Numerische Mathematik, 76 (1997), 167-188. doi: 10.1007/s002110050258. [14] A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision, 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1. [15] T. Chan and S. Esedoglu, Aspects of total variation regularized $L^1$ function approximation, SIAM Journal on Applied Mathematics, 65 (2005), 1817-1837. doi: 10.1137/040604297. [16] G. Dal Maso, I. Fonseca, G. Leoni and M. Morini, A higher order model for image restoration: The one dimensional case, SIAM Journal on Mathematical Analysis, 40 (2009), 2351-2391. doi: 10.1137/070697823. [17] F. Demengel, Fonctions à Hessien borné, Annales de l'Institut Fourier, 34 (1984), 155-190. doi: 10.5802/aif.969. [18] V. Duval, J. Aujol and Y. Gousseau, The TVL1 model: A geometric point of view, SIAM Journal on Multiscale Modeling and Simulation, 8 (2009), 154-189. doi: 10.1137/090757083. [19] I. Ekeland and R. Temam, Convex Analysis and Variational Problems, Vol. 1, North Holland, 1976. [20] M. Grasmair, The equivalence of the taut string algorithm and BV-regularization, Journal of Mathematical Imaging and Vision, 27 (2007), 59-66. doi: 10.1007/s10851-006-9796-4. [21] W. Hinterberger, M. Hintermüller, K. Kunisch, M. Von Oehsen and O. Scherzer, Tube methods for BV regularization, Journal of Mathematical Imaging and Vision, 19 (2003), 219-235. doi: 10.1023/A:1026276804745. [22] F. Knoll, K. Bredies, T. Pock and R. Stollberger, Second order total generalized variation (TGV) for MRI, Magnetic Resonance in Medicine, 65 (2011), 480-491. doi: 10.1002/mrm.22595. [23] Y. Meyer, Oscillating Patterns in Image Processing and Nonlinear Evolution Equations: The Fifteenth Dean Jacqueline B. Lewis Memorial Lectures, Vol. 22, American Mathematical Society, 2001. [24] J. Müller, Advanced Image Reconstruction and Denoising - Bregmanized (Higher Order) Total Variation and Application in PET, Ph.D thesis, University of Münster, 2013. [25] M. Nikolova, Minimizers of cost-functions involving nonsmooth data-fidelity terms. Application to the processing of outliers, SIAM Journal on Numerical Analysis, 40 (2002), 965-994. doi: 10.1137/S0036142901389165. [26] K. Papafitsoros, Novel Higher Order Regularisation Methods for Image Reconstruction, Ph.D thesis, University of Cambridge, 2014. [27] C. Pöschl and O. Scherzer, Exact solutions of one-dimensional total generalized variation, Communications in Mathematical Sciences, 13 (2015), 171-202. doi: 10.4310/CMS.2015.v13.n1.a9. [28] C. Pöschl and O. Scherzer, Characterization of minimizers of convex regularization functionals, Contemporary mathematics, 451 (2008), 219-248. doi: 10.1090/conm/451/08784. [29] W. Ring, Structural properties of solutions to total variation regularization problems, ESAIM: Mathematical Modelling and Numerical Analysis, 34 (2000), 799-810. doi: 10.1051/m2an:2000104. [30] L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D: Nonlinear Phenomena, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F. [31] D. Strong and T. Chan, Edge-preserving and scale-dependent properties of total variation regularization, Inverse Problems, 19 (2003), S165-S187. doi: 10.1088/0266-5611/19/6/059. [32] R. Temam, Mathematical Problems in Plasticity, Vol. 12, Gauthier-Villars Paris, 1983. [33] T. Valkonen, K. Bredies and F. Knoll, Total generalized variation in diffusion tensor imaging, SIAM Journal on Imaging Sciences, 6 (2013), 487-525. doi: 10.1137/120867172.

show all references

##### References:
 [1] L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems, Oxford University Press, USA, 2000. [2] H. Attouch and H. Brezis, Duality for the sum of convex functions in general Banach spaces, North-Holland Mathematical Library, 34 (1986), 125-133. doi: 10.1016/S0924-6509(09)70252-1. [3] P. Belhumeur, A binocular stereo algorithm for reconstructing sloping, creased, and broken surfaces in the presence of half-occlusion, in Proceedings of the Fourth International Conference on Computer Vision, 1993, 431-438. doi: 10.1109/ICCV.1993.378184. [4] M. Benning, Singular Regularization of Inverse Problems, Bregman Distances and Applications to Variational Frameworks with Singular Regularization Energies, Ph.D thesis, University of Münster, 2011. [5] M. Benning, C. Brune, M. Burger and J. Müller, Higher-order TV methods - Enhancement via Bregman iteration, Journal of Scientific Computing, 54 (2013), 269-310. doi: 10.1007/s10915-012-9650-3. [6] M. Benning and M. Burger, Ground states and singular vectors of convex variational regularization methods, Methods and Applications of Analysis, 20 (2013), 295-334. doi: 10.4310/MAA.2013.v20.n4.a1. [7] K. Bredies, Recovering piecewise smooth multichannel images by minimization of convex functionals with total generalized variation penalty, in Efficient Algorithms for Global Optimization Methods in Computer Vision, Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2014, 44-77. doi: 10.1007/978-3-642-54774-4_3. [8] K. Bredies and M. Holler, Artifact-free decompression and zooming of JPEG compressed images with total generalized variation, in Computer Vision, Imaging and Computer Graphics - Theory and Application, Communications in Computer and Information Science, Springer Berlin Heidelberg, 2013, 242-258. doi: 10.1007/978-3-642-38241-3_16. [9] K. Bredies, K. Kunisch and T. Pock, Total generalized variation, SIAM Journal on Imaging Sciences, 3 (2010), 492-526. doi: 10.1137/090769521. [10] K. Bredies, K. Kunisch and T. Valkonen, Properties of $L^1$-$TGV^{2}$: The one-dimensional case, Journal of Mathematical Analysis and Applications, 398 (2013), 438-454. doi: 10.1016/j.jmaa.2012.08.053. [11] K. Bredies and T. Valkonen, Inverse problems with second-order total generalized variation constraints, in Proceedings of SampTA 2011 - 9th International Conference on Sampling Theory and Applications, Singapore, 2011. [12] V. Caselles, A. Chambolle and M. Novaga, The discontinuity set of solutions of the {TV} denoising problem and some extensions, Multiscale Modeling & Simulation, 6 (2007), 879-894. doi: 10.1137/070683003. [13] A. Chambolle and P. Lions, Image recovery via total variation minimization and related problems, Numerische Mathematik, 76 (1997), 167-188. doi: 10.1007/s002110050258. [14] A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision, 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1. [15] T. Chan and S. Esedoglu, Aspects of total variation regularized $L^1$ function approximation, SIAM Journal on Applied Mathematics, 65 (2005), 1817-1837. doi: 10.1137/040604297. [16] G. Dal Maso, I. Fonseca, G. Leoni and M. Morini, A higher order model for image restoration: The one dimensional case, SIAM Journal on Mathematical Analysis, 40 (2009), 2351-2391. doi: 10.1137/070697823. [17] F. Demengel, Fonctions à Hessien borné, Annales de l'Institut Fourier, 34 (1984), 155-190. doi: 10.5802/aif.969. [18] V. Duval, J. Aujol and Y. Gousseau, The TVL1 model: A geometric point of view, SIAM Journal on Multiscale Modeling and Simulation, 8 (2009), 154-189. doi: 10.1137/090757083. [19] I. Ekeland and R. Temam, Convex Analysis and Variational Problems, Vol. 1, North Holland, 1976. [20] M. Grasmair, The equivalence of the taut string algorithm and BV-regularization, Journal of Mathematical Imaging and Vision, 27 (2007), 59-66. doi: 10.1007/s10851-006-9796-4. [21] W. Hinterberger, M. Hintermüller, K. Kunisch, M. Von Oehsen and O. Scherzer, Tube methods for BV regularization, Journal of Mathematical Imaging and Vision, 19 (2003), 219-235. doi: 10.1023/A:1026276804745. [22] F. Knoll, K. Bredies, T. Pock and R. Stollberger, Second order total generalized variation (TGV) for MRI, Magnetic Resonance in Medicine, 65 (2011), 480-491. doi: 10.1002/mrm.22595. [23] Y. Meyer, Oscillating Patterns in Image Processing and Nonlinear Evolution Equations: The Fifteenth Dean Jacqueline B. Lewis Memorial Lectures, Vol. 22, American Mathematical Society, 2001. [24] J. Müller, Advanced Image Reconstruction and Denoising - Bregmanized (Higher Order) Total Variation and Application in PET, Ph.D thesis, University of Münster, 2013. [25] M. Nikolova, Minimizers of cost-functions involving nonsmooth data-fidelity terms. Application to the processing of outliers, SIAM Journal on Numerical Analysis, 40 (2002), 965-994. doi: 10.1137/S0036142901389165. [26] K. Papafitsoros, Novel Higher Order Regularisation Methods for Image Reconstruction, Ph.D thesis, University of Cambridge, 2014. [27] C. Pöschl and O. Scherzer, Exact solutions of one-dimensional total generalized variation, Communications in Mathematical Sciences, 13 (2015), 171-202. doi: 10.4310/CMS.2015.v13.n1.a9. [28] C. Pöschl and O. Scherzer, Characterization of minimizers of convex regularization functionals, Contemporary mathematics, 451 (2008), 219-248. doi: 10.1090/conm/451/08784. [29] W. Ring, Structural properties of solutions to total variation regularization problems, ESAIM: Mathematical Modelling and Numerical Analysis, 34 (2000), 799-810. doi: 10.1051/m2an:2000104. [30] L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D: Nonlinear Phenomena, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F. [31] D. Strong and T. Chan, Edge-preserving and scale-dependent properties of total variation regularization, Inverse Problems, 19 (2003), S165-S187. doi: 10.1088/0266-5611/19/6/059. [32] R. Temam, Mathematical Problems in Plasticity, Vol. 12, Gauthier-Villars Paris, 1983. [33] T. Valkonen, K. Bredies and F. Knoll, Total generalized variation in diffusion tensor imaging, SIAM Journal on Imaging Sciences, 6 (2013), 487-525. doi: 10.1137/120867172.
 [1] Mujibur Rahman Chowdhury, Jun Zhang, Jing Qin, Yifei Lou. Poisson image denoising based on fractional-order total variation. Inverse Problems and Imaging, 2020, 14 (1) : 77-96. doi: 10.3934/ipi.2019064 [2] Denis R. Akhmetov, Renato Spigler. $L^1$-estimates for the higher-order derivatives of solutions to parabolic equations subject to initial values of bounded total variation. Communications on Pure and Applied Analysis, 2007, 6 (4) : 1051-1074. doi: 10.3934/cpaa.2007.6.1051 [3] Yunho Kim, Paul M. Thompson, Luminita A. Vese. HARDI data denoising using vectorial total variation and logarithmic barrier. Inverse Problems and Imaging, 2010, 4 (2) : 273-310. doi: 10.3934/ipi.2010.4.273 [4] Haijuan Hu, Jacques Froment, Baoyan Wang, Xiequan Fan. Spatial-Frequency domain nonlocal total variation for image denoising. Inverse Problems and Imaging, 2020, 14 (6) : 1157-1184. doi: 10.3934/ipi.2020059 [5] Rinaldo M. Colombo, Francesca Monti. Solutions with large total variation to nonconservative hyperbolic systems. Communications on Pure and Applied Analysis, 2010, 9 (1) : 47-60. doi: 10.3934/cpaa.2010.9.47 [6] Nils Dabrock, Yves van Gennip. A note on "Anisotropic total variation regularized $L^1$-approximation and denoising/deblurring of 2D bar codes". Inverse Problems and Imaging, 2018, 12 (2) : 525-526. doi: 10.3934/ipi.2018022 [7] Rustum Choksi, Yves van Gennip, Adam Oberman. Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes. Inverse Problems and Imaging, 2011, 5 (3) : 591-617. doi: 10.3934/ipi.2011.5.591 [8] Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial and Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037 [9] Raymond H. Chan, Haixia Liang, Suhua Wei, Mila Nikolova, Xue-Cheng Tai. High-order total variation regularization approach for axially symmetric object tomography from a single radiograph. Inverse Problems and Imaging, 2015, 9 (1) : 55-77. doi: 10.3934/ipi.2015.9.55 [10] Xiaoqun Zhang, Tony F. Chan. Wavelet inpainting by nonlocal total variation. Inverse Problems and Imaging, 2010, 4 (1) : 191-210. doi: 10.3934/ipi.2010.4.191 [11] Sandra Lucente. Large data solutions for semilinear higher order equations. Discrete and Continuous Dynamical Systems - S, 2020, 13 (12) : 3525-3533. doi: 10.3934/dcdss.2020247 [12] John R. Graef, Lingju Kong, Bo Yang. Positive solutions of a nonlinear higher order boundary-value problem. Conference Publications, 2009, 2009 (Special) : 276-285. doi: 10.3934/proc.2009.2009.276 [13] George J. Bautista, Ademir F. Pazoto. Decay of solutions for a dissipative higher-order Boussinesq system on a periodic domain. Communications on Pure and Applied Analysis, 2020, 19 (2) : 747-769. doi: 10.3934/cpaa.2020035 [14] John Baxley, Mary E. Cunningham, M. Kathryn McKinnon. Higher order boundary value problems with multiple solutions: examples and techniques. Conference Publications, 2005, 2005 (Special) : 84-90. doi: 10.3934/proc.2005.2005.84 [15] Robert Jankowski, Barbara Łupińska, Magdalena Nockowska-Rosiak, Ewa Schmeidel. Monotonic solutions of a higher-order neutral difference system. Discrete and Continuous Dynamical Systems - B, 2018, 23 (1) : 253-261. doi: 10.3934/dcdsb.2018017 [16] Xuewei Cui, Mei Yu. Non-existence of positive solutions for a higher order fractional equation. Discrete and Continuous Dynamical Systems, 2019, 39 (3) : 1379-1387. doi: 10.3934/dcds.2019059 [17] Aliang Xia, Jianfu Yang. Normalized solutions of higher-order Schrödinger equations. Discrete and Continuous Dynamical Systems, 2019, 39 (1) : 447-462. doi: 10.3934/dcds.2019018 [18] Alina Gleska, Małgorzata Migda. Qualitative properties of solutions of higher order difference equations with deviating arguments. Discrete and Continuous Dynamical Systems - B, 2018, 23 (1) : 239-252. doi: 10.3934/dcdsb.2018016 [19] Hiroshi Takeda. Global existence of solutions for higher order nonlinear damped wave equations. Conference Publications, 2011, 2011 (Special) : 1358-1367. doi: 10.3934/proc.2011.2011.1358 [20] Belgacem Rahal, Cherif Zaidi. On finite Morse index solutions of higher order fractional elliptic equations. Evolution Equations and Control Theory, 2021, 10 (3) : 575-597. doi: 10.3934/eect.2020081

2020 Impact Factor: 1.639