Erweiterte Suche

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 zu fördern. Diese Arbeit beschäftigt sich mit einer speziellen Art der Dünnbesetztheit, welche eine gewisse Struktur in der Lösungsmatrix favorisiert. Wir präsentieren und analysieren eine neue Regularisierung, welche lokale Dünnbesetztheit fördert, indem die l^{1,inf}-Norm in einem Variationsansatz minimiert wird. Zusätzlich analysieren wir die Asymptotik verschiedener Regularisierungsfunktionale, welche Dünngesetztheit fördern. Wir betrachten diskrete Funktionale, welche dünnbesetzte Lösungen bevorzugen, und analysieren ihr Verhalten für feiner werdende Diskretisierungen. Hierbei erhalten wir einige Gamma-Grenzwerte. Wir betrachten nicht nur l^p-Normen für p ≥ 1 sondern auch die l^0-“Norm”.

The specific field of inverse problems, where the unknown obtains apart from its spatial dimensions at least one additional dimension, is of major interest for many applications in imaging, natural sciences and medicine. Enforcing certain sparsity priors on such unknowns, which can be written as a matrix, has thus become current state of research. This thesis deals with a special type of sparsity prior, which enforces a certain structure on the unknown matrix. We present and analyze a novel regularization technique promoting so-called local sparsity by minimizing the l^{1,inf}-norm as a regularization functional in a variational approach. Furthermore, we theoretically analyze the asymptotics of spatial sparsity priors. We consider discrete sparsity promoting functionals and analyze their behavior as the discretization becomes finer. In so doing, we are able to compute some gamma-limits. We not only consider usual l^p-norms for p ≥ 1, but also analyze the asymptotics of the l^0-“norm”.

Titel: Reconstruction using local sparsity
Untertitel: a novel regularization technique and an asymptotic analysis of spatial sparsity priors
Verfasser: Heins, Pia GND
Gutachter: Burger, Martin
Organisation: FB 10: Mathematik und Informatik
Dokumenttyp: Dissertation/Habilitation
Medientyp: Text
Erscheinungsdatum: 2015
Publikation in MIAMI: 13.02.2015
Datum der letzten Änderung: 27.07.2015
Schlagwörter: 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
Fachgebiete: Mathematik
Sprache: Englisch
Format: PDF-Dokument
URN: urn:nbn:de:hbz:6-40359656702
Permalink: https://nbn-resolving.org/urn:nbn:de:hbz:6-40359656702
Onlinezugriff:
Inhalt:
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