Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The split Bregman algorithm applied to PDE-constrained optimization problems with total variation regularization

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

We derive an efficient solution method for ill-posed PDE-constrained optimization problems with total variation regularization. This regularization technique allows discontinuous solutions, which is desirable in many applications. Our approach is to adapt the split Bregman technique to handle such PDE-constrained optimization problems. This leads to an iterative scheme where we must solve a linear saddle point problem in each iteration. We prove that the spectra of the corresponding saddle point operators are almost contained in three bounded intervals, not containing zero, with a very limited number of isolated eigenvalues. Krylov subspace methods handle such operators very well and thus provide an efficient algorithm. In fact, we can guarantee that the number of iterations needed cannot grow faster than \(O([\ln (\alpha ^{-1})]^2)\) as \(\alpha \rightarrow 0\), where \(\alpha \) is a small regularization parameter. Moreover, in our numerical experiments we demonstrate that one can expect iteration numbers of order \(O(\ln (\alpha ^{-1}))\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. The exact form of the parameter \(\alpha \) is presented in the next section.

  2. Ischemia is a precursor of heart infarction.

  3. For higher order discretizations, the problem in Step 4 becomes more difficult to solve.

  4. In fact, it is possible to work with the dual space of BV with respect to the weak-* topology, which leads to the Laplacian instead of \(D'D\) in a function space as well [7, 8].

  5. Except for the presentation and discussion of Lemma 1, we simply write K instead of \(K_h\).

References

  1. Acar, R., Vogel, C.R.: Analysis of bounded variation penalty methods for ill-posed problems. Inverse Probl. 10, 1217–1229 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  2. Brègman, L.M.: A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming. Zh. vychisl. Mat. mat. Fiz 7, 620–631 (1967)

    MathSciNet  MATH  Google Scholar 

  3. Cai, J.F., Osher, S., Shen, Z.: Split Bregman methods and frame based image restoration. Multiscale Model. Simul. 8, 337–369 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  4. Chavent, G., Kunisch, K.: Regularization of linear least squares problems by total bounded variation. ESAIM 2, 359–376 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  5. Goldstein, T., Osher, S.: The split Bregman method for L1-regularized problems. SIAM J. Imaging Sci. 2, 323–343 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  6. Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 302–320 (1969)

    MathSciNet  MATH  Google Scholar 

  7. Hintermüller, M., Kunisch, K.: Totally bounded variation regularization as bilaterally constrained optimization problem. SIAM J. Appl. Math. pp. 1311–1333 (2004)

  8. Hintermüller, M., Stadler, G.: A primal-dual algorithm for TV-based inf-convolution-type image restoration. SIAM J. Sci. Comput. 28, 1–23 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  9. Mardal, K.A., Haga, J.B.: Block preconditioning of systems of PDEs. In: Logg, A., Mardal, K.A., Wells, G. (eds.) Automated Solution of Differential Equations, pp. 635–654. Springer, New York (2012)

    Google Scholar 

  10. Mardal, K.A., Winther, R.: Preconditioning discretizations of systems of partial differential equations. Numer. Linear Algebr. Appl. 18(1), 1–40 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  11. Nielsen, B.F., Mardal, K.A.: Analysis of the minimal residual method applied to ill-posed optimality systems. SIAM J. Sci. Comput. 35(2), 785–814 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  12. Nielsen, B.F., Lysaker, M., Grøttum, P.: Computing ischemic regions in the heart with the bidomain model—first steps towards validation. IEEE Trans. Med. Imaging 32, 1085–1096 (2013)

    Article  Google Scholar 

  13. Osher, S., Burger, M., Goldfarb, D., Xu, J., Yin, W.: An iterative regularization method for total variation-based image restoration. Multiscale Model. Simul. 4, 460–489 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  14. Pearson, J.W., Wathen, A.J.: A new approximation of the Schur complement in preconditioners for PDE-constrained optimization. Numer. Linear Algebr. Appl. 19(5), 816–829 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  15. Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Fletcher, R. (ed.) Optimization, pp. 283–298 (1969)

  16. Schöberl, J., Zulehner, W.: Symmetric indefinite preconditioners for saddle point problems with applications to PDE-constrained optimization problems. SIAM J. Matrix Anal. Appl. 29(3), 752–773 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  17. Schöberl, J., Simon, R., Zulehner, W.: A robust multigrid method for elliptic optimal control problems. SIAM J. Numer. Anal. 49(4), 1482–1503 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  18. Wang, D., Kirby, R.M., MacLeod, R.S., Johnson, C.R.: Inverse electrocardiographic source localization of ischemia: an optimization framework and finite element solution. J. Comput. Phys. 250, 403–424 (2013)

    Article  Google Scholar 

  19. Wu, C., Tai, X.C.: Augmented Lagrangian method, dual method and split-Bregman iterations for ROF, vectorial TV and higher order models. SIAM J. Imaging Sci. 3(3), 300–339 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  20. Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for L1-minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1(1), 143–168 (2008)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors would like to thank the FEniCS community for their work on the automatic solution of PDEs. We are also grateful for the comments provided by the referees, which significantly improved this article. This work was supported by the The Research Council of Norway, Project Number 239070.

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences and Technology, Norwegian University of Life Sciences, Ås, Norway

    Ole Løseth Elvetun & Bjørn Fredrik Nielsen

Authors
  1. Ole Løseth Elvetun
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bjørn Fredrik Nielsen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ole Løseth Elvetun.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Elvetun, O.L., Nielsen, B.F. The split Bregman algorithm applied to PDE-constrained optimization problems with total variation regularization. Comput Optim Appl 64, 699–724 (2016). https://doi.org/10.1007/s10589-016-9823-3

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-016-9823-3

Keywords

Search

Navigation