Adaptive Wavelet Methods for Inverse Problems: Acceleration Strategies, Adaptive Rothe Method and Generalized Tensor Wavelets

In general, inverse problems can be described as the task of inferring conclusions about the cause u from given observations y of its effect. This can be described as the inversion of an operator equation K(u) = y, which is assumed to be ill-posed or ill-conditioned. To arrive at a meaningful soluti...

Ausführliche Beschreibung

Gespeichert in:
1. Verfasser: Friedrich, Ulrich
Beteiligte: Dahlke, Stephan (Prof. Dr.) (BetreuerIn (Doktorarbeit))
Format: Dissertation
Veröffentlicht: Philipps-Universität Marburg 2014
Reine und Angewandte Mathematik
Online Zugang:PDF-Volltext
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!


2. R. Haller-Dintelmann and J. Rehberg, Maximal parabolic regularity for diver- gence operators including mixed boundary conditions, J. Differential Equations 247 (2009), no. 5, 1354–1396.

3. K. Ito, B. Jin, and J. Zou, A two-stage method for inverse medium scattering, J. Comput. Phys. 237 (2013), 211–223.

4. M. Bachmayr and W. Dahmen, Adaptive near-optimal rank tensor approxima- tion for high-dimensional operator equations, Found. Comput. Math. (2014), 1–60.

5. I. Daubechies, M. Defrise, and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math. 57 (2004), no. 11, 1413–1457.

6. Y. Fomekong-Nanfack, J.A. Kaandorp, and J. Blom, Efficient parameter estima- tion for spatio-temporal models of pattern formation: Case study of Drosophila melanogaster, Bioinformatics 23 (2007), no. 24, 3356–3363.

7. [25] , Numerical Analysis of Wavelet Methods, Studies in Mathematics and its Applications, vol. 32, North-Holland, Amsterdam, 2003. Bibliography

8. R.E. Showalter, Monotone Operators in Banach Space and Nonlinear Partial Differential Equations, Math. Surveys Monogr., vol. 49, American Mathematical Society, Providence, 1997.

9. T. Apel, Anisotropic Finite Elements: Local Estimates and Applications. Ad- vances in Numerical Mathematics, Teubner, Stuttgart, 1999.

10. J.-L. Starck, D.L. Donoho, and E.J. Candès, Astronomical image representation by the curvelet transform, Astron. Astrophys. 398 (2003), no. 2, 785–800.

11. P. Morin, R.H. Nochetto, and K.G. Siebert, Convergence of adaptive finite el- ement methods, SIAM Rev. 44 (2002), no. 4, 631–658.

12. R. Ramlau, G. Teschke, and M. Zhariy, A compressive Landweber iteration for solving ill-posed inverse problems, Inverse Problems 24 (2008), no. 6, 26.

13. [27] , Adaptive wavelet methods II — Beyond the elliptic case, Found. Com- put. Math. 2 (2002), no. 3, 203–245.

14. W. Dahmen, Wavelet and multiscale methods for operator equations, Acta Nu- mer. 6 (1997), 55–228.

15. G. Teschke and C. Borries, Accelerated projected steepest descent method for nonlinear inverse problems with sparsity constraints, Inverse Problems 26 (2010), no. 2, 23.

16. R.E. Bank and A. Weiser, Some a posteriori error estimators for elliptic partial differential equations, Math. Comp. 44 (1985), no. 170, 283–301.

17. Dahlke, W. Dahmen, R. Hochmuth, and R. Schneider, Stable multiscale bases and local error estimation for elliptic problems, Appl. Numer. Math. 23 (1997), no. 1, 21–47.

18. P. D'Haeseleer, X. Wen, S. Fuhrman, and R. Somogyi, Linear modeling of mRNA expression levels during CNS development and injury, Pac. Symp. Bio- comput. 4 (1999), 41–52.

19. R.A. DeVore, Nonlinear approximation, Acta Numer. 7 (1998), 51–150.

20. [44] , Wavelets on manifolds. I. Construction and domain decomposition, SIAM J. Math. Anal. 31 (1999), no. 1, 184–230.

21. [28] , Adaptive wavelet schemes for nonlinear variational problems, SIAM J. Numer. Anal. 41 (2003), no. 5, 1785–1823.

22. T. Chen, H.L. He, and G.M. Church, Modeling gene expression with differential equations, Pac. Symp. Biocomput. 4 (1999), 29–40.

23. M. Figueiredo and R. Nowak, An EM algorithm for wavelet-based image restora- tion, IEEE Trans. Image Process. 12 (2003), no. 8, 906–916.

24. R.P. Stevenson, Adaptive solution of operator equations using wavelet frames, SIAM J. Numer. Anal. 41 (2003), no. 3, 1074–1100.

25. Dahlke and W. Sickel, On Besov regularity of solutions to nonlinear elliptic partial differential equations, Rev. Mat. Complut. 26 (2013), no. 1, 115–145.

26. R.A. Ressel, A Parameter Identification Problem Involving a Nonlinear Parabolic Differential Equation, Ph.D. thesis, Univ. Bremen, 2012.

27. B. Jin and P. Maass, Sparsity regularization for parameter identification prob- lems, Inverse Problems 28 (2012), no. 12, 123001, 70.

28. T.J. Dijkema, Adaptive Tensor Product Wavelet Methods for Solving PDEs, Ph.D. thesis, Univ. Utrecht, 2009.

29. D. Jerison and C.E. Kenig, The inhomogeneous Dirichlet problem in Lipschitz domains, J. Funct. Anal. 130 (1995), no. 1, 161–219.

30. J.L. Lions, Optimal Control of Systems Governed by Partial Differential Equa- tions, Grundlehren Math. Wiss., vol. 170, Springer-Verlag, Berlin -Heidelberg -New York, 1971.

31. W. Dahmen and R. Schneider, Wavelets with complementary boundary condi- tions — function spaces on the cube, Results Math. 34 (1998), no. 3–4, 255–293.

32. T. Bonesky, K. Bredies, D.A. Lorenz, and P. Maass, A generalized conditional gradient method for nonlinear operator equations with sparsity constraints, In- verse Problems 23 (2007), no. 5, 2041–2058.

33. C. Lubich and A. Ostermann, Linearly implicit time discretization of non-linear parabolic equations, IMA J. Numer. Anal. 15 (1995), no. 4, 555–583.

34. A. Cohen, Wavelet methods in numerical analysis, Solution of Equation in R (Part 3), Techniques of Scientific Computing (Part 3), Handb. Numer. Anal., vol. VII, North-Holland, Amsterdam, 2000, pp. 417–711.

35. K. Eriksson and C. Johnson, Adaptive finite element methods for parabolic prob- lems. I. A linear model problem, SIAM J. Numer. Anal. 28 (1991), no. 1, 43–77. [57] , Adaptive finite element methods for parabolic problems. II. Optimal error estimates in L ∞ L 2 and L ∞ L ∞ , SIAM J. Numer. Anal. 32 (1995), no. 3, 706–740.

36. W. Dörfler, A convergent adaptive algorithm for Poisson's equation, SIAM J. Numer. Anal. 33 (1996), no. 3, 1106–1124.

37. P.C. Hansen and D. O'Leary, The use of the L-curve in the regularization of discrete ill-posed problems, SIAM J. Sci. Comput. 14 (1993), no. 6, 1487–1503.

38. N. Chegini and R.P. Stevenson, Adaptive wavelet schemes for parabolic prob- lems: Sparse matrices and numerical results, SIAM J. Numer. Anal. 49 (2011), no. 1, 182–212.

39. [119] , On the compressibility of operators in wavelet coordinates, SIAM J. Math. Anal. 35 (2004), no. 5, 1110–1132.

40. J.G. Verwer, E.J. Spee, J.G. Blom, and W. Hundsdorfer, A second-order Rosen- brock method applied to photochemical dispersion problems, SIAM J. Sci. Com- put. 20 (1999), no. 4, 1456–1480.

41. A. Chambolle, R.A. DeVore, N. Lee, and B.J. Lucier, Nonlinear wavelet im- age processing: Variational problems, compression, and noise removal through wavelet shrinkage, IEEE Trans. Image Process. 7 (1998), no. 3, 319–335.

42. Dahlke, M. Fornasier, T. Raasch, R.P. Stevenson, and M. Werner, Adaptive frame methods for elliptic operator equations: the steepest descent approach, IMA J. Numer. Anal. 27 (2007), no. 4, 717–740.

43. N.G. Chegini and R.P. Stevenson, The adaptive tensor product wavelet scheme: Sparse matrices and the application to singularly perturbed problems, IMA J. Numer. Anal. 32 (2012), no. 1, 75–104.

44. K. Berberian, Lectures in Functional Analysis and Operator Theory, Grad. Texts in Math., vol. 15, Springer-Verlag, Berlin -Heidelberg -New York, 1974.

45. R. Griesse and D.A. Lorenz, A semismooth Newton method for Tikhonov func- tionals with sparsity constraints, Inverse Problems 24 (2008), no. 3, 035007, 19.

46. M. Grasmair, M. Haltmeier, and O. Scherzer, Sparse regularization with l q penalty term, Inverse Problems 24 (2008), no. 5, 055020, 13.

47. B. Kaltenbacher, F. Schöpfer, and T. Schuster, Iterative methods for nonlinear ill-posed problems in Banach spaces: Convergence and applications to parameter identification problems, Inverse Problems 25 (2009), no. 6, 065003, 19.

48. T. Schuster, B. Hofmann, and B. Kaltenbacher, Tackling inverse problems in a Banach space environment: From theory to applications, Inverse Problems 28 (2012), no. 10, 100201.

49. H.-J. Bungartz and M. Griebel, Sparse grids, Acta Numer. 13 (2004), 147–269.

50. A. Shapiro, On concepts of directional differentiability, J. Optim. Theory Appl. 66 (1990), no. 3, 477–487.

51. W. Dahmen, R. Schneider, and Y. Xu, Nonlinear functionals of wavelet expan- sions — adaptive reconstruction and fast evaluation, Numer. Math. 86 (2000), no. 1, 49–101.

52. R. Ramlau and G. Teschke, A Tikhonov-based projection iteration for nonlinear ill-posed problems with sparsity constraints, Numer. Math. 104 (2006), no. 2, 177–203.

53. P.-A. Nitsche, Sparse approximation of singularity functions, Constr. Approx. 21 (2005), no. 1, 63–81.

54. [97] , Best N -term approximation spaces for tensor product wavelet bases, Constr. Approx. 24 (2006), no. 1, 49–70.

55. T.J. Dijkema, C. Schwab, and R.P. Stevenson, An adaptive wavelet method for solving high-dimensional elliptic PDEs, Constr. Approx. 30 (2009), no. 3, 423–455.

56. Y. Nesterov, Gradient methods for minimizing composite functions, Math. Pro- gram. 140 (2013), no. 1, Ser. B, 125–161.

57. [120] , Optimality of a standard adaptive finite element method, Found. Com- put. Math. 7 (2007), no. 2, 245–269.

58. V. Thomée, Galerkin Finite Element Methods for Parabolic Problems, 2nd ed., Springer Ser. Comput. Math., vol. 25, Springer-Verlag, Berlin, 2006.

59. M. Werner, Adaptive wavelet frame domain decomposition methods for elliptic operator equations, Ph.D. thesis, Univ. Marburg, 2009.

60. [121] , Adaptive wavelet methods for solving operator equations: An overview, Multiscale, Nonlinear and Adaptive Approximation. Dedicated to Wolfgang Dahmen on the Occasion of his 60th Birthday, Springer-Verlag, Berlin, 2009, pp. 543–597.

61. A. Kirsch, An Introduction to the Mathematical Theory of Inverse Problems, 2nd ed., Appl. Math. Sci., vol. 120, Springer-Verlag, New York, 2011. Bibliography

62. F.A. Bornemann, B. Erdmann, and R. Kornhuber, A posteriori error estimates for elliptic problems in two and three space dimensions, SIAM J. Numer. Anal. 33 (1996), no. 3, 1188–1204.

63. [127] , A Review of a Posteriori Error Estimation and Adaptive Mesh- Refinement Techniques, Chichester: Wiley; Stuttgart: Teubner, 1996.

64. [112] , Fast evaluation of nonlinear functionals of tensor product wavelet ex- pansions, Numer. Math. 119 (2011), no. 4, 765–786.

65. J. Bergh and J. Löfström, Interpolation Spaces. An Introduction, Grundlehren Math. Wiss., vol. 223, Springer-Verlag, Berlin -Heidelberg -New York, 1976.

66. H. Amann, Linear and Quasilinear Parabolic Problems. Vol. 1: Abstract Linear Theory, Monogr. Math., vol. 189, Birkhäuser, Basel, 1995.

67. K. Strehmel and R. Weiner, Linear-implizite Runge-Kutta-Methoden und ihre Anwendung, Teubner-Texte Math., vol. 127, Teubner, Stuttgart, 1992.

68. W. Arendt, R. Chill, S. Fornaro, and C. Poupaud, L p -maximal regularity for non-autonomous evolution equations, J. Differential Equations 237 (2007), no. 1, 1–26.

69. S. Dahlke, W. Dahmen, and R.A. DeVore, Nonlinear approximation and adap- tive techniques for solving elliptic operator equations, Multiscale Wavelet Meth- ods for Partial Differential Equations, Wavelet Anal. Appl., vol. 6, Academic Press, San Diego, 1997, pp. 237–283.

70. J. Appell and P.P. Zabrejko, Nonlinear Superposition Operators, Cambridge Tracts in Math., vol. 95, Cambridge University Press, Cambridge, 1990.

71. C. Johnson, Numerical Solution of Partial Differential Equations by the Finite Element Method, Dover Publications Inc., Mineola, 2009.

72. I. Loris, On the performance of algorithms for the minimization of l 1 -penalized functionals, Inverse Problems 25 (2009), no. 3, 035008, 16.

73. L.C. Evans, Partial Differential Equations, 2nd ed., Grad. Stud. Math., vol. 19, American Mathematical Society, Providence, 2010.

74. T. Kato, Perturbation Theory for Linear Operators, Reprint of the Corr. 2nd ed., Classics Math., Springer-Verlag, Berlin -Heidelberg -New York, 1995.

75. T. Schuster, B. Kaltenbacher, B. Hofmann, and K.S. Kazimierski, Regulariza- tion Methods in Banach Spaces, Radon Ser. Comput. Appl. Math, vol. 10, De Gruyter, Berlin, 2012.

76. A. Pazy, Semigroups of Linear Operators and Applications to Partial Differen- tial Equations, Appl. Math. Sci., vol. 44, Springer-Verlag, New York, 1983.

77. E. Hairer, S.P. Nørsett, and G. Wanner, Solving Ordinary Differential Equa- tions. I. Nonstiff Problems, 2nd rev. ed., Springer Ser. Comput. Math., vol. 8, Springer-Verlag, Berlin, 1993.

78. Z. Ciesielski and T. Figiel, Spline bases in classical function spaces on compact C ∞ manifolds. Part I and II, Studia Math. 76 (1983), no. 1–2, 1–58, 95–136.

79. K. Urban, Wavelet methods for elliptic partial differential equations, Numeri- cal Mathematics and Scientific Computation, Oxford University Press, Oxford, 2009.

80. A. Cohen, W. Dahmen, and R.A. DeVore, Adaptive wavelet methods for elliptic operator equations: Convergence rates, Math. Comp. 70 (2001), no. 233, 27–75.

81. P. Binev, W. Dahmen, and R.A. DeVore, Adaptive finite element methods with convergence rates, Numer. Math. 97 (2004), no. 2, 219–268.

82. Dahlke, E. Novak, and W. Sickel, Optimal approximation of elliptic problems by linear and nonlinear mappings. I, J. Complexity 22 (2006), no. 1, 29–49.

83. B. Jin, T. Khan, and P. Maass, A reconstruction algorithm for electrical impedance tomography based on sparsity regularization, Internat. J. Numer. Methods Engrg. 89 (2012), no. 3, 337–353.

84. V.G. Maz'ya and J. Roßmann, Weighted L p estimates of solutions to boundary value problems for second order elliptic systems in polyhedral domains, ZAMM Z. Angew. Math. Mech. 83 (2003), no. 7, 435–467.

85. Dahlke, M. Fornasier, and T. Raasch, Multilevel preconditioning for adaptive sparse optimization, Preprint 25, DFG Priority Program 1324, 2009. [36] , Multilevel preconditioning and adaptive sparse solution of inverse prob- lems, Math. Comp. 81 (2012), no. 277, 419–446.

86. M.R. Hestenes, Extension of the range of a differentiable function, Duke Math. J. 8 (1941), no. 1, 183–192.

87. P. Hansbo and C. Johnson, Adaptive finite element methods in computational mechanics, Comput. Methods Appl. Mech. Engrg. 101 (1992), no. 1–3, 143–181.

88. Dahlke, Besov regularity for elliptic boundary value problems in polygonal domains, Appl. Math. Lett. 12 (1999), no. 6, 31–36.

89. A. Barinka, Fast Computation Tools for Adaptive Wavelet Schemes, Ph.D. the- sis, RWTH Aachen, 2005.

90. A. Kunoth and J. Sahner, Wavelets on manifolds: An optimized construction, Math. Comp. 75 (2006), no. 255, 1319–1349.

91. M. Crouzeix and V. Thomée, On the discretization in time of semilinear parabolic equations with nonsmooth initial data, Math. Comp. 49 (1987), no. 180, 359–377.

92. [43] , Composite wavelet bases for operator equations, Math. Comp. 68 (1999), no. 228, 1533–1567.

93. C. Schwab and R.P. Stevenson, Adaptive wavelet algorithms for elliptic PDEs on product domains, Math. Comp. 77 (2008), no. 261, 71–92. Bibliography [111] , Space-time adaptive wavelet methods for parabolic evolution problems, Math. Comp. 78 (2009), no. 267, 1293–1318.

94. N.G. Chegini, S. Dahlke, U. Friedrich, and R.P. Stevenson, Piecewise tensor product wavelet bases by extensions and approximation rates, Math. Comp. 82 (2013), no. 284, 2157–2190.

95. Y. Fomekong-Nanfack, M. Postma, and J.A. Kaandorp, Inferring Drosophila gap gene regulatory network: A parameter sensitivity and perturbation analysis, BMC Syst. Biol. 3 (2009), no. 1, 94.

96. D.A. Lorenz, Convergence rates and source conditions for Tikhonov regular- ization with sparsity constraints, J. Inverse Ill-Posed Probl. 16 (2008), no. 5, 463–478.

97. I. Babuška and W.C. Rheinboldt, A survey of a posteriori error estimators and adaptive approaches in the finite element method, Proceedings of the China- France Symposium on Finite Element Methods (Beijing, 1982), Sci. Press Bei- jing, Beijing, 1983, pp. 1–56.

98. I. Babuška, Advances in the p and h-p versions of the finite element method. A survey, Numerical Mathematics Singapore 1988, Internat. Ser. Numer. Math., vol. 86, Birkhäuser, Basel, 1988, pp. 31–46.

99. D.A. Lorenz, P. Maass, and P.Q. Muoi, Gradient descent for Tikhonov func- tionals with sparsity constraints: Theory and numerical comparison of step size rules, Electron. Trans. Numer. Anal. 39 (2012), 437–463.

100. E.C. Lai, P. Tomancak, R.W. Williams, and G.M. Rubin, Computational iden- tification of Drosophila microRNA genes, Genome Biol. 4 (2003), no. 7, R42.

101. J. Reinitz and D. Sharp, Mechanism of eve stripe formation, Mech. Dev. 49 (1995), no. 1–2, 133–158.

102. W. Sickel and T. Ullrich, Tensor products of Sobolev-Besov spaces and applica- tions to approximation from the hyperbolic cross, J. Approx. Theory 161 (2009), no. 2, 748–786.

103. E. Mjolsness, D. Sharp, and J. Reinitz, A connectionist model of development, J. Theor. Biol. 152 (1991), no. 4, 429–453.

104. J.-L. Starck, M.K. Nguyen, and F. Murtagh, Wavelets and curvelets for image deconvolution: A combined approach, Signal Process. 83 (2003), no. 10, 2279– 2283.

105. K. Ito and K. Kunisch, Semi-smooth Newton methods for state-constrained op- timal control problems, Systems Control Lett. 50 (2003), no. 3, 221–228.

106. C. Canuto, A. Tabacco, and K. Urban, The wavelet element method. Part II. Realization and additional features in 2D and 3D, Appl. Comput. Harmon. Anal. 8 (2000), no. 2, 123–165.

107. W. Dahmen, A. Kunoth, and K. Urban, Biorthogonal spline-wavelets on the interval — stability and moment conditions, Appl. Comput. Harmon. Anal. 6 (1999), no. 6, 132–196.

108. J. Kappei, Adaptive frame methods for nonlinear elliptic problems, Appl. Anal. 90 (2011), no. 8, 1323–1353.

109. M. Primbs, Stabile biorthogonale Spline-Waveletbasen auf dem Intervall, Ph.D. thesis, Univ. Duisburg-Essen, 2006. [100] , New stable biorthogonal spline-wavelets on the interval, Results Math. 57 (2010), no. 1–2, 121–162.

110. M. Costabel, M. Dauge, and S. Nicaise, Analytic regularity for linear elliptic systems in polygons and polyhedra, Tech. report, Cornell University Library, 2011.

111. R. Verfürth, A posteriori error estimation and adaptive mesh-refinement tech- niques, J. Comput. Appl. Math. 50 (1994), no. 1-3, 67–83.

112. M. Dauge and R.P. Stevenson, Sparse tensor product wavelet approximation of singular functions, SIAM J. Math. Anal. 42 (2010), no. 5, 2203–2228.

113. J. Lang, Adaptive Multilevel Solution of Nonlinear Parabolic PDE Systems. Theory, Algorithm, and Applications, Lect. Notes Comput. Sci. Eng., vol. 16, Springer-Verlag, Berlin, 2001.