title: Adaptive Wavelet Methods for Inverse Problems: Acceleration Strategies, Adaptive Rothe Method and Generalized Tensor Wavelets
title: Adaptive Wavelet Methoden für Inverse Probleme: Beschleunigungsstrategien, Adaptive Rothe Methode und Verallgemeinerte Tensor-Wavelets
Creators: name: Friedrich, Ulrich
Publisher: name: Philipps-Universität Marburg
Year: 2015
Subjects: subject: adaptive Rothe Method
subject: Inverse Problems
subject: Mathematics
subject: FOS: Mathematics
subject: adaptive wavelet Verfahren
subject: Tensor wavelets
subject: adaptive Rothe Methode
subject: Inverse Probleme
subject: Wavelet
subject: Tensor Wavelets
subject: iterative thresholding
subject: adaptive wavelet schemes

description: 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.
description: Allgemein kann man inverse
      Probleme als die Aufgabe beschreiben, aus gegebenen Daten y
      Rückschlüsse auf deren Ursache u zu ziehen. Dies kann als die
      Inversion einer nichtlinearen Operatorgleichung K(u) = y
      beschrieben werden, die im Allgemeinen schlecht konditioniert
      oder schlecht gestellt ist. Um zu einem sinnvollen
      Lösungsbegriff zu kommen, werden Regularisierungstechniken
      eingesetzt. Als Näherungslösung des inversen Problems
      akzeptiert man bei der sogenannten Tikhonov Regularisierung
      einen Minimierer v der Summe aus Datenfehler K(v)-y (in einer
      geeigneten Norm) und einem gewichteten zusätzlichen Strafterm
      F(v). Die Entwicklung von effizienten Lösungsverfahren zur
      Berechnung der Minimierer ist ein Feld aktueller Forschung
      und ein zentraler Aspekt dieser Thesis. Typischerweise kommen
      hier verallgemeinerte Gradientenabstiegsverfahren zum
      Einsatz. Für gewichtete lp-Norm Strafterme F führen diese auf
      iterative Soft-Shrinkage-Verfahren. Ohne zusätzliche Annahmen
      ist die Konvergenz üblicherweise nur für eine Teilfolge und
      dann auch nur gegen einen stationären Punkt gewährleistet.
      Über die Regularisierungseigenschaften dieses Punktes ist nur
      wenig bekannt. Die beobachtete Konvergenzgeschwindigkeit des
      klassischen Soft-Shrinkage-Verfahrens ist in der Praxis sehr
      gering. In jedem Iterationsschritt müssen sowohl der
      nichtlineare Operator K als auch die Adjungierte seiner
      Ableitung ausgewertet werden, was numerisch sehr aufwändig
      ist. Diese Thesis beschäftigt sich deshalb mit der
      Entwicklung von Beschleunigungsverfahren für inverse
      Probleme, kombiniert mit dem Einsatz und der
      Weiterentwicklung effizienter Verfahren für die Auswertung
      der auftretenden nichtlinearen Operatoren. Ein erstes
      Ergebnis dieser Thesis ist eine allgemeine
      Beschleunigungsstrategie für die Soft-Shrinkage-Iteration zur
      Berechnung der Lösung von inversen Problemen. Sie beruht auf
      einer streng monoton abfallenden Wahl für die Gewichte des
      Strafterms. Das neue Verfahren konvergiert linear gegen den
      gesuchten Minimierer v. Eine sehr wichtige Klasse von
      inversen Problemen stellen Parameteridentifikationsprobleme
      für partielle Differentialgleichungen dar. Als Prototyp für
      diese Problemklasse wird ein spezielles
      Parameteridentifikationsproblem für eine parabolische
      partielle Differentialgleichung betrachtet. Die auftretenden
      Operatoren werden analysiert, die Anwendbarkeit der Tikhonov
      Regularisierung sicher gestellt und die Parameter in einem
      vereinfachten Testproblem rekonstruiert. Zur numerischen
      Behandlung der parabolische Differentialgleichungen kommt die
      sogenannte horizontale Linienmethode, die oft auch als Rothes
      Methode bezeichnet wird, zum Einsatz. Hierbei wird das
      parabolische Gleichung als abstraktes Cauchy Problem
      aufgefasst und zunächst, üblicherweise implizit, in der Zeit
      diskretisiert. Dies wird dann mit einer Ortsdiskretisierung
      der resultierenden S-stufigen räumlichen Systeme kombiniert.
      Um zu einem effizienten numerischen Verfahren zu gelangen
      werden in dieser Thesis adaptive numerische Verfahren zur
      Lösung der Stufengleichungen betrachtet. Die Konvergenz
      dieser inexakten Rothe Methode wird im Detail analysiert.
      Insbesondere wird der Fall betrachtet das realisierbare
      asymptotisch optimale Diskretisierungsverfahren, die auf
      Wavelet Basen beruhen, zum Einsatz kommen. Es wird eine obere
      Schranke für die Gesamtkomplexität des Verfahrens
      hergeleitet. Im Detail wird das Beispiel der
      Wärmeleitungsgleichung betrachtet. Diese führt auf
      elliptische Stufengleichungen für deren Lösungen ein neues
      Regularitätsresultat bewiesen wird. Die Konvergenzrate von
      asymptotisch optimalen adaptiven Verfahren hängt
      üblicherweise reziprok von der Raumdimension des zu lösenden
      Problems ab, was auch als Fluch der Dimensionalität
      bezeichnet wird. Einen Ausweg bilden sogenannten
      Tensor-Wavelet Diskretisierungen die auf
      dimensionsunabhängige Raten führen. Die klassische
      Tensor-Wavelet Konstruktion ist auf Produktgebiete
      beschränkt. In dieser Thesis wird eine verallgemeinerte
      Tensor-Wavelet Basiskonstruktion für Sobolev Räume über einem
      Gebiet mit relativ allgemeiner Geometrie entwickelt. Die
      Konstruktion basiert auf der Anwendung von
      Fortsetzungsoperatoren auf passende Basen auf Teilgebieten,
      die eine nichtüberlappende Gebietszerlegung des
      Gesamtgebietes bilden. Die bestmögliche Approximation von
      Funktionen mittels der neuen Basis reproduziert die von
      klassischen Tensor-Wavelets bekannte dimensionsunabhängige
      Konvergenzrate. Die Regularitätsannahmen sind für die Lösung
      elliptischer Gleichungen der Ordnung 2m=2 über einem
      polygonalen oder polyhedralen Gebiet für genügend glatte
      rechte Seiten gewährleistet. Numerische Tests belegen, dass
      die theoretisch optimale Rate in der Praxis auch realisiert
      wird.