Adaptive frame based regularization methods for linear ill-posed inverse problems [Elektronische Ressource] / von Mariya Zhariy

AdaptiveFrameBasedRegularizationMethods
forLinearIll-PosedInverseProblems

vonMariyaZhariy

Dissertionat

zurErlangungdesakademischenGrades
haftenNaturwissenscderDoktorin–Dr.rer.nat.–

VorgelegtimFachbereichIIIderUniversit¨atBremen
2008erOktobim

Betreuer:Prof.Dr.GerdTeschke
Prof.Dr.RonnyRamlau

Abstract

Thisthesisisconcernedwiththedevelopmentandanalysisofadaptiveregularizationmethodsforsolving
linearinverseill-posedproblems.Basedonnonlinearapproximationtheory,theadaptivityconcepthas
becomepopularinthefieldofwell-posedproblems,especiallyinthesolutionofellipticPDE’s.Under
certainconditionsonthesmoothnessofthesolutionandthecompressibilityoftheoperatorithasbeen
shownthatthenonlinearapproximationguaranteesamoreefficientapproximationwithrespecttothe
sparsityofthesolutionandtothecomputationaleffort.
Intheareaofinverseproblems,thesparseapproximationapproachhasbeenappliedinsolvingde-
noisingandde-blurringproblemsaswellasingeneralregularization.Anessentialcostreductionhas
beenachievedbynewlydevelopedstrategieslikedomaindecompositionandspecificprojectionmeth-
ods.However,theoptionofadaptiveapplication,leadingsimultaneouslytocostreductionandsparse
approximation,hasnotbeentakenintoaccountyet.
Inourresearchwecombinetheadvantagesofthenonlinearapproximationwiththeclassicalregular-
izationandparameteridentificationstrategies,likeTikhonovandLandwebermethods.Wemodifythe
classicalapproachforsolvingtheill-posedinverseproblemsinordertoobtainasparseapproximation
withessentiallyreducednumericaleffort.Themainnoveltyofthedevelopedregularizationmethodsis
theadaptiveoperatorapproximation.
Ingeneral,wehaveshownthatitispossibletoconstructadaptiveregularizationmethods,whichyield
thesameconvergenceratesastheconventionalregularizationmethods,butaremuchmoreefficientwith
respecttothenumericalcosts.
Theanalyticresultsofthisworkhavebeenconfirmedandcomplementedbynumericalexperiments,that
illustratethesparsityoftheobtainedsolutionanddesiredconvergencerates.

Zusammenfassung

DasHauptvorhabendieserArbeitistdieEntwicklungadaptiverRegularisierungsmethodenf¨urdieL¨osung
linearerschlechtgestellterinverserProbleme.BasierendaufdernichtlinearenApproximationhabenadap-
tiveVerfahrenindenletztenJahreninsbesondereimBereichdergutgestelltenProblemeanPopularit¨at
gewonnen.UnterbestimmtenVoraussetzungenandieGlattheitderL¨osungunddieKompressibilit¨atdes
OperatorsistesgelungendieL¨osungeinesgutgestelltenProblemsdurcheined¨unnbesetzteDarstellung
mitlinearerKomplexit¨atzuapproximieren.
InderletztenZeitsinddieaufderd¨unnenDarstellungbasiertenAns¨atzeaufdemGebietderschlecht-
gestelltenProblememehrmalserfolgreichverwendetworden,etwaimBereichderVerbesserungder
Bildqualit¨atdurchEntrauschenundSch¨arfen.DiedarauffolgendentwickeltennumerischenVerfahren,
wiez.B.GebietzerlegungsalgorithmenoderbestimmteProjektionsstrategien,erm¨oglicheneineSenkung
derIterationsschritte,ber¨ucksichtigenabernichtdieM¨oglichkeitderadaptivenAnwendung.
DieindieserArbeitvorgestelltenadaptivenRegularisierungsverfahrenbasierenaufdenklassischenMeth-
odenzurL¨osungschlechtgestellterProbleme,etwaLandweber-IterationundTikhonov-Regularisierung
sowieentsprechenderRegelnzurWahlderoptimalenRegularisierungsparameter.DieModifikationder
klassischenVerfahrenerfolgtmitdemZiel,dieL¨osungderschlechtgestelltenProblemeaufeineadaptive
WeisezuapproximierenundgleichzeitigdenBerechnungsaufwandzureduzieren.Dabeientstehenauf
nat¨urlicheWeised¨unnbesetzteRekonstruktionen.
DietheoretischenResultatederArbeitwurdenanhandeinesnumerischenBeispiels,derRekonstruktion
vonTomographie-Daten,verifiziert.Esistunsgelungen,denRechenaufwandzuverringernunddabei
dieKonvergenzratendernichtadaptivenVerfahrenzuerhalten.

tsentCon

IWaveletBasesAndFramesForOperatorEquations
1WaveletBases
1.1MultiresolutionandWaveletRieszBases............................
1.2RieszBasisPropertyandBiorthogonality...........................
1.3CharacterizationofFunctionSpaces..............................
1.3.1FunctionSpaces.....................................
1.3.2DirectandInverseEstimates..............................
1.4WaveletsonBoundedDomains.................................
2Frames
2.1BasicFrameTheory.......................................
2.2GelfandFrames..........................................
2.3LocalizationofFrames......................................
2.4FrameBasedOperatorDiscretization..............................

IIInverseProblems
B3Definitionsasic3.1Ill-PosednessandGeneralizedInverse..............................
3.2RegularizationandOrderOptimality..............................
3.3CompactLinearOperators...................................
4FilterBasedFormulation
4.1RegularizationPropertyandParameterChoiceRules.....................
4.1.1A-prioriParameterChoice................................
4.1.2Morozov’sDiscrepancyPrinciple............................
4.1.3BalancingPrinciple...................................
4.2RegularizationinHilbertScales.................................
4.2.1WaveletBasedRegularization..............................
4.3TikhonovRegularization.....................................
4.3.1RegularizationResult..................................
4.3.2TikhonovRegularizationwithanA-PrioriParameterChoice............
4.3.3TikhonovRegularizationwithMorozov’sDiscrepancyPrinciple...........
4.3.4TikhonovRegularizationwithBalancingPrinciple..................
4.3.5TikhonovRegularizationinHilbertScales.......................
4.4LandweberIteration.......................................
4.4.1RegularizationResult..................................

5779011131411771910202

3225522682312323333353738393939304040414

4.4.2A-prioriTruncationRule................................
4.4.3Morozov’sDiscrepancyPrinciple............................
4.4.4LandweberIterationinHilbertscales.........................

IIIAdaptivityIssues
5NonlinearApproximationandAdaptivity
5.1NonlinearApproximation....................................
5.2BestN-termApproximationin2................................
6AdaptiveIterativeSchemeforWell-PosedProblems
6.1FrameBasedSetting.......................................
6.2AdaptiveDiscretizationoftheOperatorEquation.......................
6.3FrameBasedAdaptiveSolver..................................

IVAdaptiveRegularizationMethods
7ApproximateFilterBasedMethods
7.1ApproximateFilterBasedRegularization...........................
7.1.1ApproximateWaveletBasedRegularization......................
7.2ApproximateMorozov’sDiscrepancyPrinciple........................
7.3OrderOptimalitybyApproximateBalancingPrinciple....................
8AdaptiveTikhonovRegularization
8.1AdaptiveTikhonovRegularization:Formulation.......................
8.1.1RegularizationResult..................................
8.2OrderOptimalitybyA-prioriParameterChoice........................
8.2.1StandardFilterBasedMethod.............................
8.2.2A-prioriErrorEstimateinHilbertscales........................
8.3ComplexityofAdaptiveTikhonovRegularization.......................
8.4ApproximateApplicationofBalancingPrinciple.......................
9AdaptiveLandweberIteration
9.1ModifiedLandweberIteration..................................
9.2AdaptiveFormulationofLandweberIteration.........................
9.3OrderOptimalitybyA-PrioriParameterChoice.......................
9.4RegularizationbyA-PosterioriParameterChoice.......................
9.4.1AdaptiveResidualDiscrepancy.............................
9.4.2AMonotonicityofAdaptiveIteration.........................
9.4.3ConvergenceinExactDataCase............................
9.4.4RegularizationResult..................................
roblemPExample1010.1LinearRadonTransform.....................................
10.2RegularityofSolution......................................
10.3RequirementsontheSystem..................................
10.3.1RequirementsImposedbytheRegularityoftheSolution...............
10.3.2RequirementsImposedbytheOperatorDiscretization................

141424

4345546494940515

7559061626367696960707071727373747678787871848911929393959

11

4.01

Numerics

10.4.1

Summary

.............................................

Adaptive

and

Discretization

Outlo

ok

.................................

79

79

105

ductiontroIn

Adaptivityisapromisingconceptinsignalrepresentationwheneverastructureorasignalundercon-
siderationisinsomesensesparse,i.e.itcanbeapproximatedbyonlyafewcomponentsintermsof
somebasisorframe.Themaintwoquestionsinsparseapproximationarehowtofindanappropriate
decomposingsystemandwhichcomponentstouse.
Inthisthesisweapplytheconceptofnonlinearapproximation[28]intermsofwavelets,whichhasits
origininthemultiresolutionanalysis[20,40].Themultiscaledecompositionbenefitsfromthesimultane-
ousrepresentationofthesignalcomponentsondifferentresolutionlevels,whichinmanyrelevantcases
resultsinamoreefficientapproximationthantherepresentationonthefinestresolutionlevel.However,
givenamultileveldecomposition,therearedifferentwaystoapproximatethedecomposedsignalfrom
itsbuildingcomponents.Theefficiencyofapproximationcanbeconsiderablyimprovedifoneconsiders
significantcomponentsofthesignalinsteadofworkingwithlinearsubspaces,builtbytruncationin
scale.Unlikethelevel-by-levelapproximati