C02
Digital Representations of Manifold Data


Whenever data is processed using computers, analog-to-digital (A/D) conversion, that is, representing the data using just 0s and 1s, is a crucial ingredient of the procedure. This project will mathematically study approaches to this problem for data with geometric structural constraints.

Mission-

Investigating how well geometric objects can be represented using bit streams

Scientific Details+

Many results in mathematical data analysis follow the paradigm of increasing efficiency by incorporating structural assumptions on the underlying data. The most prominent models today are sparsity models and manifold models in high dimensional data analysis. One main goal in these scenarios is a faithful analog to digital conversion, which not only requires a discretization, but also a digitalization step, often termed quantization, as only a finite number of bits can be processed.

A key aspect in finding suitable methods for digitally representing data is a careful balance between the resolution of this quantization step and the redundancy of the underlying discretization. Arguably the most popular class of suitable quantization schemes for highly redundant settings are so-called Sigma-Delta modulators. The underlying idea is to quantize recursively and then deduce recovery guarantees from the stability of the resulting discrete dynamical system. Variants are available for bandlimited signals, for frame representations, and for compressed sensing. For manifold models, however, there is very little quantization literature available. Project C02 aims to fill this gap, attempting a systematic study of quantization under manifold constraints.

The following three viewpoints shall be investigated:

  • Functions on manifolds: This work package is devoted to quantized representations of functions whose domain is a manifold. We will study bandlimited functions and also discuss applications to digital halftoning on manifolds.
  • Data lying on a manifold: We aim to study redundancies resulting from the fact that high dimensional data lies on a or close to a known manifold. We aim to incorporate quantization into the compressed sensing methodology for manifold models, as they have recently received attention in the literature.

Geometric and topological properties: Our question here is to what extent the manifold as a whole or its important geometric and topological properties can be recovered despite quantization. This project part will closely interact with project C04, which studies a related problem without quantization.

Publications+

Papers
  • F. Krahmer, C. Kuehn, and N. Sissouno.
    Predicting sparse circle maps from their dynamics.
    preprint, January 2020.
    arXiv:1911.06312.
  • Olga Graf, Felix Krahmer, and Sara Krause-Solberg.
    One-Bit Sigma-Delta modulation on the circle.
    preprint, November 2019.
    dgd:587.
  • Olga Graf, Ayush Bhandari, and Felix Krahmer.
    One-Bit Unlimited Sampling.
    In Proc. IEEE Intl. Conf. Acoustics Speach Signal Proc. (ICASSP 2019). September 2019.
    doi:10.1109/ICASSP.2019.8683266, dgd:442.
  • M. Iwen, S. Dirksen, J. Maly, and S. Krause-Solberg.
    Robust One-bit Compressed Sensing With Manifold Data.
    In Proc. Intl. Conf. on Sampling Theory and Applications (SampTA '19). September 2019.
    URL: https://sampta2019.sciencesconf.org/267528/document.
  • Sandra Keiper.
    Approximation of generalized ridge functions in high dimensions.
    Journal of Approximation Theory, 245:101–129, 2019.
    doi:10.1016/j.jat.2019.04.006.
  • O. Graf, F. Krahmer, and S. Krause-Solberg.
    Higher order 1-bit Sigma-Delta modulation on a circle.
    In Proc. Intl. Conf. on Sampling Theory and Applications (SampTA '19). 2019.
    URL: https://sampta2019.sciencesconf.org/273036/document.
  • Ayush Bhandari, Felix Krahmer, and Ramesh Raskar.
    On Unlimited Sampling and Reconstruction.
    Preprint, 2019.
    arXiv:1905.03901.
  • F. Krahmer, C. Kühn, and N. Sissouno.
    Predicting sparse circle maps from their dynamics.
    preprint, 2019.
    arXiv:1911.06312.
  • Axel Flinth and Sandra Keiper.
    Recovery of binary sparse signals with biased measurement matrices.
    IEEE Transactions on Information Theory, 2019.
    doi:10.1109/TIT.2019.2929192.
  • Sara Krause-Solberg, Olga Graf, and Felix Krahmer.
    One-Bit Sigma-Delta Modulation on a Closed Loop.
    2018 IEEE Statistical Signal Processing Workshop (SSP), pages 208–212, August 2018.
    URL: https://ieeexplore.ieee.org/document/8450721, doi:10.1109/SSP.2018.8450721.
  • Tomas Sauer Mariantonia Cotronei, Caroline Moosmüller and Nada Sissouno.
    Level-Dependent Interpolatory Hermite Subdivision Schemes and Wavelets.
    Constructive Approximation, July 2018.
    doi:10.1007/s00365-018-9444-4.
  • Mark A. Iwen, Felix Krahmer, Sara Krause-Solberg, and Johannes Maly.
    On Recovery Guarantees for One-Bit Compressed Sensing on Manifolds.
    preprint, July 2018.
    arXiv:arXiv:1807.06490v1.
  • B. Bodmann, A. Flinth, and G. Kutyniok.
    Compressed Sensing for Analog Signals.
    preprint, March 2018.
    arXiv:1803.04218.
  • R. Reisenhofer, S. Bosse, G. Kutyniok, and T. Wiegand.
    A Haar Wavelet-Based Perceptual Similarity Index for Image Quality Assessment.
    Signal Proc. Image Comm., 61:33–43, February 2018.
    arXiv:1607.06140, doi:10.1016/j.image.2017.11.001.
  • S. Keiper, G. Kutyniok, D. G. Lee, and G. E. Pfander.
    Compressed sensing for finite-valued signals.
    Linear Algebra and its Applications, 532:570–613, November 2017.
    arXiv:1609.09450, doi:10.1016/j.laa.2017.07.006.
  • M. Genzel, G. Kutyniok, and M. März.
    $\ell ^1$-Analysis Minimization and Generalized (Co-)Sparsity: When Does Recovery Succeed?
    preprint, October 2017.

Posters
  • Felix Krahmer Sara Krause-Solberg, Olga Graf.
    One-bit sigma-delta modulation on a closed loop.
    november 2018. poster.
    dgd:443.

Team+

Prof. Dr. Felix Krahmer    +

Projects: C02
University: TU München
E-Mail: Felix.Krahmer[at]ma.tum.de


Prof. Dr. Gitta Kutyniok   +

Projects: C03, C02
University: LMU München
E-Mail: kutyniok[at]math.lmu.de
Website: http://www.math.tu-berlin.de/?108957
University: LMU München
E-Mail: kutyniok[at]math.lmu.de


Olga Graf   +

Projects: C02
University: TU München
E-Mail: graf[at]ma.tum.de