Abstract

The total generalized variation (TGV) is a popular regularizer in inverse problems and imaging combining discontinuous solutions and higher order smoothing. In particular, empirical observations suggest that its order two version strongly favors piecewise affine functions. In the present manuscript, we formalize this statement for the one-dimensional TGV-functional by characterizing the extremal points of its sublevel sets with respect to a suitable quotient space topology. These results imply that 1D TGV-regularized linear inverse problems with finite dimensional observations admit piecewise affine minimizers. As further applications of this characterization we include precise first-order necessary optimality conditions without requiring convexity of the fidelity term, and a simple solution algorithm for TGV-regularized minimization problems.

Author information

Contact details are reproduced from the original publication and may be historical.

José A. Iglesias

Johann Radon Inst. for Computational and Applied Mathematics, Austrian Academy of Sciences, Linz, Austria

jose.iglesias@ricam.oeaw.ac.at

Daniel Walter

Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Linz, Austria

daniel.walter@ricam.oeaw.ac.at

Keywords

  • Total generalized variation
  • regularization
  • extremal points
  • non-smooth optimization
  • sparsity

Mathematics Subject Classification

46A55, 90C49, 65J20, 52A40

References

  1. L. Ambrosio, N. Fusco, D. Pallara: Functions of Bounded Variation and Free Discontinuity Problems, Oxford Mathematical Monographs, Oxford University Press, New York (2000).https://doi.org/10.1093/oso/9780198502456.001.0001Google Scholar
  2. C. Boyer, A. Chambolle, Y. De Castro, V. Duval, F. De Gournay, P. Weiss: On representer theorems and convex regularization, SIAM J. Optimization 29/2 (2019) 1260–1281.https://doi.org/10.1137/18M1200750Google Scholar
  3. K. Bredies, M. Carioni: Sparsity of solutions for variational inverse problems with finite-dimensional data, Calc. Var. Partial Diff. Equations 59/1 (2020), art. no. 14.https://doi.org/10.1007/s00526-019-1658-1Google Scholar
  4. K. Bredies, M. Carioni, S. Fanzon, D. Walter: Linear convergence of accelerated generalized conditional gradient methods, arXiv: 2110.06756 (2021).Google Scholar
  5. K. Bredies, M. Holler: Regularization of linear inverse problems with total generalized variation, J. Inverse Ill-Posed Problems 22/6 (2014) 871–913.https://doi.org/10.1515/jip-2013-0068Google Scholar
  6. K. Bredies, M. Holler: Higher-order total variation approaches and generalisations, Inverse Problems 36/12 (2020), art. no. 123001, 128 pp.https://doi.org/10.1088/1361-6420/ab8f80Google Scholar
  7. K. Bredies, K. Kunisch, T. Pock: Total generalized variation, SIAM J. Imaging Sci. 3/3 (2010) 492–526.https://doi.org/10.1137/090769521Google Scholar
  8. K. Bredies, K. Kunisch, T. Valkonen: Properties of L1 -TGV2 : The one-dimensional case, J. Math. Analysis Appl. 398/1 (2013) 438–454.https://doi.org/10.1016/j.jmaa.2012.08.053Google Scholar
  9. K. Bredies, T. Valkonen: Inverse problems with second-order total generalized variation constraints, in: Proceedings of the 9th International Conference on Sampling Theory and Applications (SampTA), Singapore 2011, arXiv: 2005.09725 (2020).Google Scholar
  10. E. Casas, C. Clason, K. Kunisch: Parabolic control problems in measure spaces with sparse solutions, SIAM J. Control Optimization 51/1 (2013) 28–63.https://doi.org/10.1137/120872395Google Scholar
  11. A. Chambolle, T. Pock: A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision 40/1 (2011) 120–145.https://doi.org/10.1007/s10851-010-0251-1Google Scholar
  12. J. C. De los Reyes, E. Loayza-Romero: Total generalized variation regularization in data assimilation for Burgers’ equation, Inverse Probl. Imaging 13/4 (2019) 755–786.https://doi.org/10.3934/ipi.2019035Google Scholar
  13. Y. Dong, T. Görner, S. Kunis: An algorithm for total variation regularized photoacoustic imaging, Adv. Comput. Math. 41/2 (2015) 423–438.https://doi.org/10.1007/s10444-014-9364-1Google Scholar
  14. J. C. Dunn: Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals, SIAM J. Control Optimization 17/2 (1979) 187–211.https://doi.org/10.1137/0317015Google Scholar
  15. V. Duval, J.-F. Aujol, Y. Gousseau: The TVL1 model: a geometric point of view, Multiscale Model. Simul. 8/1 (2009) 154–189.https://doi.org/10.1137/090757083Google Scholar
  16. M. Fabian, P. Habala, P. Hájek, V. Montesinos Santalucía, J. Pelant, V. Zizler: Functional Analysis and Infinite-Dimensional Geometry, CMS Books in Mathematics 8, Springer, New York (2001).https://doi.org/10.1007/978-1-4757-3480-5Google Scholar
  17. M. Freiberger, C. Clason, M. Scharfetter: Total variation regularization for nonlinear fluorescence tomography with an augmented Lagrangian splitting approach, Appl. Opt. 49/19 (2010) 3741–3747.https://doi.org/10.1364/AO.49.003741Google Scholar
  18. D. Kitahara, L. Condat, A. Hirabayashi: One-dimensional edge-preserving spline smoothing for estimation of piecewise smooth functions, in: ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2019) 5611–5615.https://doi.org/10.1109/ICASSP.2019.8683260Google Scholar
  19. H. Kuroda, M. Yamagishi, I. Yamada: Exploiting sparsity in tight-dimensional spaces for piecewise continuous signal recovery, IEEE Trans. Signal Processing 66/24 (2018) 6363–6376.https://doi.org/10.1109/TSP.2018.2876328Google Scholar
  20. S. Lacoste-Julien: Convergence rate of Frank-Wolfe for non-convex objectives, arXiv: 1607.00345 (2016).Google Scholar
  21. Y. Nesterov: Introductory Lectures on Convex Optimization, Applied Optimization 87, Kluwer Academic Publishers, Boston (2004).https://doi.org/10.1007/978-1-4419-8853-9Google Scholar
  22. G. Ongie, M. Jacob: Recovery of discontinuous signals using group sparse higher degree total variation, IEEE Signal Process. Lett. 22/9 (2015) 1414–1418.https://doi.org/10.1109/LSP.2015.2407321Google Scholar
  23. K. Papafitsoros, K. Bredies: A study of the one dimensional total generalised variation regularisation problem, Inverse Probl. Imaging 9/2 (2015) 511–550.https://doi.org/10.3934/ipi.2015.9.511Google Scholar
  24. K. Papafitsoros, T. Valkonen: Asymptotic behaviour of total generalised variation, in: Scale Space and Variational Methods in Computer Vision, Lecture Notes in Computer Science 9087, Springer, Berlin (2015) 702–714.https://doi.org/10.1007/978-3-319-18461-6_56Google Scholar
  25. C. Pöschl, O. Scherzer: Exact solutions of one-dimensional total generalized variation, Commun. Math. Sci. 13/1 (2015) 171–202.https://doi.org/10.4310/CMS.2015.v13.n1.a9Google Scholar
  26. L. I. Rudin, S. Osher, E. Fatemi: Nonlinear total variation based noise removal algorithms, Physica D. Nonlin. Phen. 60/1-4 (1992) 259–268.https://doi.org/10.1016/0167-2789(92)90242-FGoogle Scholar
  27. I. W. Selesnick: Generalized total variation: tying the knots, IEEE Signal Process. Lett. 22/11 (2015) 2009–2013.https://doi.org/10.1109/LSP.2015.2449297Google Scholar
  28. T. Valkonen: The jump set under geometric regularisation. Part 2: Higher-order approaches, J. Math. Analysis Appl. 453/2 (2017) 1044–1085.https://doi.org/10.1016/j.jmaa.2017.04.037Google Scholar

Suggested citation

J. A. Iglesias, D. Walter. “Extremal Points of Total Generalized Variation Balls in 1D: Characterization and Applications.” Journal of Convex Analysis 29 (2022), No. 4, 1251–1290. https://doi.org/10.68381/jca29068

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2022. Rights now held by Banach Press LLC.