Reconstruction using local sparsity : a novel regularization technique and an asymptotic analysis of spatial sparsity priors

Das Gebiet der inversen Probleme, wobei die Unbekannte neben ihrer örtlichen Dimension mindestens noch eine zusätzliche Dimension enthält, ist bedeutend für viele Anwendungen wie z.B. Bildgebung, Naturwissenschaften und Medizin. Es hat sich durchgesetzt dünnbesetzte Matrizen (Sparsity) als Lösungen...

Author: Heins, Pia
Further contributors: Burger, Martin (Thesis advisor)
Division/Institute:FB 10: Mathematik und Informatik
Document types:Doctoral thesis
Media types:Text
Publication date:2015
Date of publication on miami:13.02.2015
Modification date:27.07.2015
Edition statement:[Electronic ed.]
Subjects:Lokale Sparsity; Inverse Probleme; Regularisierung; Variationsmethoden; Bildgebung; Asymptotische Sparsity; Radon-Maße Local Sparsity; Inverse Problems; Compressed Sensing; Regularization Theory; Imaging; Asymptotic Sparsity; Radon Measures
DDC Subject:510: Mathematik
License:InC 1.0
Language:English
Format:PDF document
URN:urn:nbn:de:hbz:6-40359656702
Permalink:http://nbn-resolving.de/urn:nbn:de:hbz:6-40359656702
Digital documents:diss_heins.pdf
Table of contents:
  • 1 Introduction 21
  • 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
  • 1.2 Inverse Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
  • 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
  • 1.4 Organization of this Work . . . . . . . . . . . . . . . . . . . . . . . . . . 27
  • 2 Mathematical Preliminaries 31
  • 2.1 Variational Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
  • 2.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
  • 2.1.2 Γ-Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
  • 2.2 Function Spaces and Sequence Spaces . . . . . . . . . . . . . . . . . . 37
  • 2.2.1 Basic Measure Theory . . . . . . . . . . . . . . . . . . . . . . . . 38
  • 2.2.2 Lebesgue Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 40
  • 2.2.3 Sequence Spaces lp . . . . . . . . . . . . . . . . . . . . . . . . . 41
  • 2.2.4 Sobolev Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
  • 2.2.5 Space of Functions with Bounded Variation . . . . . . . . . . . . 43
  • 2.2.6 Space of Finite Radon Measures . . . . . . . . . . . . . . . . . . 46
  • 2.3 Convex Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
  • 2.3.1 Subdifferential Calculus . . . . . . . . . . . . . . . . . . . . . . . 52
  • 2.3.2 Legendre-Fenchel Duality . . . . . . . . . . . . . . . . . . . . . . 55
  • 2.4 Introduction to Sparsity . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
  • 2.4.1 l0-Regularization . . . . . . . . . . . . . . . . . . . . . . . . . . 58
  • 2.4.2 l1-Regularization . . . . . . . . . . . . . . . . . . . . . . . . . . 60
  • 2.4.3 Regularization with Radon Measures . . . . . . . . . . . . . . . . 61
  • 3 Mixed Norms and Structured Sparsity 63
  • 3.1 Introduction to Mixed lp,q-Norms . . . . . . . . . . . . . . . . . . . . . . 64
  • 3.2 Sparsity and Mixed Norms . . . . . . . . . . . . . . . . . . . . . . . . . 68
  • 3.2.1 Joint Sparsity via lp,1-Regularizations . . . . . . . . . . . . . . . . 69
  • 3.2.2 Local Sparsity via l1,q-Regularizations . . . . . . . . . . . . . . . 70
  • 4 Analysis of l1,∞- Related Formulations 73
  • 4.1 Basic Properties and Formulations . . . . . . . . . . . . . . . . . . . . . 74
  • 4.1.1 Problem Formulations . . . . . . . . . . . . . . . . . . . . . . . . 75
  • 4.1.2 Existence and Uniqueness . . . . . . . . . . . . . . . . . . . . . 77
  • 4.1.3 Subdifferentials and Source Conditions . . . . . . . . . . . . . . 80
  • 4.1.4 Equivalence of Formulations . . . . . . . . . . . . . . . . . . . . 86
  • 4.1.5 Asymptotic 1-Sparsity . . . . . . . . . . . . . . . . . . . . . . . . 93
  • 4.2 Exact Recovery of Locally 1-Sparse Solutions . . . . . . . . . . . . . . . . 97
  • 4.2.1 Lagrange Functional and Optimality Conditions . . . . . . . . . . 98
  • 4.2.2 Scaling Conditions for Exact Recovery . . . . . . . . . . . . . . . 98
  • 4.3 Further Improvement by Including Total Variation . . . . . . . . . . . . . 103
  • 5 Algorithms Promoting Local Sparsity 105
  • 5.1 Algorithm for l1,∞-l1,1-Regularized Problems . . . . . . . . . . . . . . . . 105
  • 5.1.1 Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . . 107
  • 5.1.2 Stopping Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . 108
  • 5.1.3 Adaptive Parameter Choice . . . . . . . . . . . . . . . . . . . . . 109
  • 5.1.4 Solving the l1,∞-l1,1-Regularized Problem . . . . . . . . . . . . . 111
  • 5.2 Algorithms for l1,∞-l1,1-TV-Regularized Problems . . . . . . . . . . . . . . 112
  • 5.2.1 Additional TV-Regularization on the Image . . . . . . . . . . . . . 112
  • 5.2.2 Additional TV-Regularization on the Coefficient Matrices . . . . . 119
  • 6 Computational Experiments 127
  • 6.1 Application to Dynamic Positron Emission Tomography . . . . . . . . . . 127
  • 6.2 Results for Synthetic Examples . . . . . . . . . . . . . . . . . . . . . . . 131
  • 6.3 Reconstruction Including Total Variation . . . . . . . . . . . . . . . . . . 135
  • 6.3.1 Additional Total Variation on the Image . . . . . . . . . . . . . . 135
  • 6.3.2 Additional Total Variation on the Coefficient Matrices . . . . . . . 138
  • 7 Asymptotics of Spatial Sparsity Priors 143
  • 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
  • 7.2 Spatial Sparsity under Γ-Convergence . . . . . . . . . . . . . . . . . . . 144
  • 7.2.1 Convergence for the Convex Case p ≥ 1 . . . . . . . . . . . . . . 146
  • 7.2.2 Convergence for the Nonconvex Case p = 0 . . . . . . . . . . . . 151
  • 7.3 Asymptotics of Mixed Norms . . . . . . . . . . . . . . . . . . . . . . . . 154
  • 7.3.1 Convergence for the General Convex Case . . . . . . . . . . . . . 156
  • 7.3.2 Asymptotic Local Sparsity . . . . . . . . . . . . . . . . . . . . . . 157
  • 8 Deconvolution of Sparse Spikes 161
  • 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
  • 8.2 Deconvolution of a Single δ-Spike . . . . . . . . . . . . . . . . . . . . . 163
  • 8.3 Algorithm for Sparse Spikes Deconvolution . . . . . . . . . . . . . . . . 167
  • 8.4 Numerical Deconvolution of Three δ-Spikes . . . . . . . . . . . . . . . . 170
  • 9 Conclusions and Outlook 173
  • 9.1 Local Sparsity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
  • 9.2 Sparsity Asymptotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
  • A Solving the Positive l1,∞ − l1,1-Projection-Problem 177
  • B Inequality for Stopping Criteria 183
  • C Computation Of The Kinetic Modeling Matrix 187
  • D Exact l1-Reconstruction of 1-Sparse Signals in 1D 189
  • Bibliography 191.