Dokument

Summary:
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 solution in this setting, regularization schemes need to be applied. One of the most important regularization methods is the so called Tikhonov regularization. As an approximation to the unknown truth u it is possible to consider the minimizer v of the sum of the data error K(v)-y (in a certain norm) and a weighted penalty term F(v). The development of efficient schemes for the computation of the minimizers is a field of ongoing research and a central Task in this thesis. Most computation schemes for v are based on some generalized gradient descent approach. For problems with weighted lp-norm penalty terms this typically leads to iterated soft shrinkage methods. Without additional assumptions the convergence of these iterations is only guaranteed for subsequences, and even then only to stationary points. In general, stationary points of the minimization problem do not have any regularization properties. Also, the basic iterated soft shrinkage algorithm is known to converge very poorly in practice. This is critical as each iteration step includes the application of the nonlinear operator K and the adjoint of its derivative. This in itself may already be numerically demanding. This thesis is concerned with the development of strategies for the fast computation of the solution of inverse problems with provable convergence rates. In particular, the application and generalization of efficient numerical schemes for the treatment of the arising nonlinear operator equations is considered. The first result of this thesis is a general acceleration strategy for the iterated soft thresholding iteration to compute the solution of the inverse problem. It is based on a decreasing strategy for the weights of the penalty term. The new method converges with linear rate to a global minimizer. A very important class of inverse problems are parameter identification problems for partial differential equations. As a prototype for this class of problems the identification of parameters in a specific parabolic partial differential equation is investigated. The arising operators are analyzed, the applicability of Tikhonov Regularization is proven and the parameters in a simplified test equation are reconstructed. The parabolic differential equations are solved by means of the so called horizontal method of lines, also known as Rothes method. Here the parabolic problem is interpreted as an abstract Cauchy problem. It is discretized in time by means of an implicit scheme. This is combined with a discretization of the resulting system of spatial problems. In this thesis the application of adaptive discretization schemes to solve the spatial subproblems is investigated. Such methods realize highly nonuniform discretizations. Therefore, they tend to require much less degrees of freedom than classical discretization schemes. To ensure the convergence of the resulting inexact Rothe method, a rigorous convergence proof is given. In particular, the application of implementable asymptotically optimal adaptive methods, based on wavelet bases, is considered. An upper bound for the degrees of freedom of the overall scheme that are needed to adaptively approximate the solution up to a prescribed tolerance is derived. As an important case study, the complexity of the approximate solution of the heat equation is investigated. To this end a regularity result for the spatial equations that arise in the Rothe method is proven. The rate of convergence of asymptotically optimal adaptive methods deteriorates with the spatial dimension of the problem. This is often called the curse of dimensionality. One way to avoid this problem is to consider tensor wavelet discretizations. Such discretizations lead to dimension independent convergence rates. However, the classical tensor wavelet construction is limited to domains with simple product geometry. Therefor, in this thesis, a generalized tensor wavelet basis is constructed. It spans a range of Sobolev spaces over a domain with a fairly general geometry. The construction is based on the application of extension operators to appropriate local bases on subdomains that form a non-overlapping domain decomposition. The best m-term approximation of functions with the new generalized tensor product basis converges with a rate that is independent of the spatial dimension of the domain. For two- and three-dimensional polytopes it is shown that the solution of Poisson type problems satisfies the required regularity condition. Numerical tests show that the dimension independent rate is indeed realized in practice.

Bibliographie / References

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.

Das Dokument ist im Internet frei zugänglich - Hinweise zu den Nutzungsrechten