Approximation of Signals and Functions in High Dimensions
with Low Dimensional Structure
– Finite-Valued Sparse Signals and Generalized Ridge
Functions –
vorgelegt von
SANDRA KEIPER (M.Sc.)
an der Fakultät II – Mathematik und Naturwissenschaften
der Technischen Universität Berlin
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
– Dr. rer. nat. –
genehmigte Dissertation
Promotionsausschuss:
Vorsitzender: Prof. Dr. Martin Henk
Gutachterin: Prof. Dr. Gabriele Steidl
Gutachter: Prof. Dr. Massimo Fornasier
Gutachter: Prof. Dr. Jan Vybíral
Tag der wissenschaftlichen Aussprache: 01. Oktober 2020
Berlin 2020
Abstract
In this thesis, we consider the following class of high dimensional functions
f:X→R,f(x) = g(dist(x,L)),
where Lis a linear subspace of a usually high dimensional space X=RNand g:Ω⊂
R→Ris a function with certain properties. We study different reconstruction problems
under additional assumptions on gand L.
In the papers [54,41,56] (see Appendix A – C), we assume that gis a multiple of
the identity map and Lis some (N−1)-dimensional subspace. We further consider the
signed distance, so that fbecomes f(x) = hx,ai, where a∈RNis orthogonal to L. If ais
a sparse vector, this problem is well-known from compressed sensing. In this context we
study different reconstruction problems.
In Appendix A, [54], we assume that a∈RNis sparse and finite-valued. We present
an approach that incorporates a finite values prior into basis pursuit, which is one clas-
sical reconstruction strategy in compressed sensing. In particular, we address unipolar
binary and bipolar ternary sparse signals, i.e., sparse signals with entries in {0, 1}, or
in {−1,0,1}respectively. We show that phase transition takes place earlier than using
the classical basis pursuit approach and that, independently of the sparsity of the sig-
nal, at most N/2, respectively 3N/4, measurements are necessary to recover a unipolar
binary, and a bipolar ternary signal uniquely. We further discuss robustness with re-
spect to noisy measurements and generalizations to signals with entries in larger alpha-
bets. In this work we consider Gaussian measurements yi=hxi,ai,i=1, . . . , m, where
[x1, . . . , xm]∈Rm,Nis a Gaussian matrix.
In Appendix B, [41], we concentrate on the recovery of sparse, (unipolar) binary signals
through box-constrained basis pursuit. In contrast to the work in Appendix A we use bi-
ased measurement matrices, whose entries have a nonzero expected value. This enables
us, using a probabilistic model, to provide conditions under which the recovery of both
s-sparse and saturated, i.e., (N−s)-sparse binary signals, is very likely. In fact, we also
show that under the same conditions, the solution of the boxed-constrained basis pursuit
program can be found using boxed-constrained least squares, which has some practical
impact. This allows for example to establish stability without a-priori knowledge on the
noise level.
In Appendix C, [56], we also study the reconstruction of binary sparse signals from bi-
ased measurements. In contrast to the work in Appendix B, however, we consider biased
partial random circulant instead of fully random measurements. We again show that the
reconstruction via the least-squares strategy is as good as the reconstruction via the usu-
ally used program basis pursuit. We further show that we need as many measurements
to recover an s-sparse signal x0∈RNas we need to recover a saturated signal, more-
precisely an (N−s)-sparse signal x0∈RN. We further establish stability with respect to
noisy measurements.
Then, in [55], we consider the case that L⊆RNis an unknown linear subspace of X
and g:R→Ris also an unknown map. Note that in the case that Lis an (N−1)-
dimensional subspace, this problem is known in the context of so-called ridge functions.
Thus, in Appendix D, [55], "we study the approximation of generalized ridge func-
iii
tions, namely of functions which are constant along some submanifolds of RN. We in-
troduce the notion of linear-sleeve functions, whose function values only depend on the
distance to some unknown linear subspace L. We propose two effective algorithms to ap-
proximate linear-sleeve functions f(x) = g(dist(x,L)2), when both the linear subspace
L⊂RNand the function g∈Cs[0,1]are unknown. We prove error bounds for both
algorithms and provide an extensive numerical comparison of both. We further discuss
an approach to apply these algorithms to capture general sleeve functions, which depend
on the distance to some lower dimensional submanifold."
iv
Zusammenfassung in deutscher Sprache
In dieser Dissertation betrachten wir die folgende Klasse von Funktionen
f:X→R,f(x) = g(dist(x,L)),
wobei Lein linearer Unterraum des typischerweise hochdimensionalen Raumes X=RN
ist und g:Ω⊂R→Reine Funktion, die weitere Eigenschaften hat. Unter zusätzlichen
Voraussetzungen an gund Luntersuchen wir in diesem Zusammenhang unterschiedli-
che Rekonstruktionsprobleme.
In den Veröffentlichungen [54,41,56] (siehe Appendix A – C) nehmen wir zusätzlich
an, dass gein Vielfaches der Identitätsabbildung ist und dass Lein (N−1)-dimensionaler
Unterraum von RNist. Darüber hinaus werden wir die signierte Distanz anstelle der
normalen Distanz betrachten. Dadurch vereinfacht sich die Funktion fzu f(x) = hx,ai,
wobei a∈RNorthogonal zu List. Unter der Voraussetzung, dass a∈RNdünn besetzt
ist, also viele Einträge Null sind, ist dieses Problem sehr bekannt im Compressed Sensing
Bereich. In diesem Kontext untersuchen wir drei verschiedene Probleme.
In [54] (siehe Appendix A), nehmen wir an, dass a∈RNdünn besetzt ist und dass
die Einträge von aaus einem endlichen Alphabet stammen. Wir präsentieren einen An-
satz zur Lösung des Problems, in welchem die Endlichkeit des Alphabets als Prior in
die sogenannte `1-Minimierung, als Rekonstruktionsmethode, eingebaut wird. Die `1-
Minimierung ist eine klassische Methode, die im Bereich des Compressed Sensing viel
Anwendung findet.
Insbesondere betrachten wir unipolare binäre und bipolar ternäre Signale, also Signale
mit Einträgen in den Alphabeten {0, 1}beziehungsweise {−1, 0,1}. Wir zeigen, dass die
sogenannte „Phase Transition“früher stattfindet als bei der klassischen `1-Minimierung
und dass, unabhängig von der dünnen Besetzung des Signals, N/2 beziehungsweise
3N/4 Messungen ausreichen, um ein unipolar binäres oder bipolar ternäres Signal ein-
deutig zu rekonstruieren. Darüber hinaus diskutieren wir die Robustheit des Algorith-
mus sowie Verallgemeinerungen auf Signale mit Einträgen aus größeren Alphabeten. In
dieser Arbeit betrachten wir insbesondere Gauß-Messungen yi=hxi,ai,i=1, . . . , m,
wobei [x1, . . . , xm]∈Rm,Neine Gauß-Matrix ist.
In [41] (siehe Appendix B), konzentrieren wir uns auf die Rekonstruktion von dünn
besetzen, (unipolar) binären Signalen mittels `1-Minimierungen unter sogenannten Box-
Bedingungen, also der Bedingung, dass die Einträge des zu rekonstruierenden Signals
in der Box [0, 1]liegen müssen. Im Gegensatz zu der Arbeit in Appendix A benutzen
wir verschobene zufällige Messmatrizen, deren Einträge einen von Null verschieden Er-
wartungswert haben. Dies versetzt uns in die Lage, Bedingungen zu erarbeiten, unter
denen die Rekonstruktion eines s-dünnen binären Signals genauso gut funktioniert, wie
die Rekonstruktion eines (N−s)-dünnen, also unter Umständen dicht besetzten, binären
Signals. Weiterhin zeigen wir sogar, dass unter denselben Bedingungen die Lösung der
`1-Minimierung mit Box-Bedingungen genauso durch die Kleinste-Quadrate-Methode
mit Box-Bedingungen gefunden werden kann. Das hat einige praktische Vorteile, da es
uns beispielsweise erlaubt, Robustheit zu zeigen, ohne die Größenordnung der Störung
vorher zu kennen.
In [56] (siehe Appendix C), betrachten wir ebenso die Rekonstruktion von binären Sig-
nalen aus verschobenen zufälligen Messungen. Statt komplett randomisierter Matrizen
v
Loading more pages...