Approximation of signals and functions in high dimensions with low dimensional structure: finite-valued sparse signals and generalized ridge functions

In this thesis, we consider the class of high dimensional functions which contains functions which are defined in high-dimensional spaces but are known to be constant along some unknown manifolds. We study different reconstruction problems under additional assumptions. In the papers [54, 41, 56] (see Appendix A – C), we consider this problem in the context of compressed sensing and study the following problems. In Appendix A, [54], we assume that we aim to reconstruct a sparse and finite-valued vector. We present an approach that incorporates a finite values prior into basis pursuit, which is one classical reconstruction strategy in compressed sensing. In particular, we address unipolar binary and bipolar ternary sparse signals. We show that phase transition takes place earlier than using the classical basis pursuit approach and that, independently of the sparsity of the signal, 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 respect to noisy measurements and generalizations to signals with entries in larger alphabets. In this work we consider Gaussian measurements. 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 biased 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 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 biased 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 usually used program basis pursuit. We further show that we need as many measurements to recover an sparse signal as we need to recover a saturated signal. We further establish stability with respect to noisy measurements. Then, in [55],we study the approximation of generalized ridge functions, namely of functions which are constant along some submanifolds. We introduce the notion of linear-sleeve functions, whose function values only depend on the distance to some unknown linear subspace. We propose two effective algorithms to approximate linear-sleeve functions. 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.

Author dc:creator

• Keiper, Sandra

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Identifier URI

http://dx.doi.org/10.14279/depositonce-10636

OAI identifier oai:identifier

oai:depositonce.tu-berlin.de:11303/11748