On unlimited sampling and reconstruction: a new way to sense the continuum

Abstract

In this work, we introduce the Unlimited Sensing framework which is a novel, non-linear sensing architecture that allows for recovery of an arbitrarily high dynamic range, continuous-time signal from its low dynamic range, digital measurements. Our work is based on a radically different ADC design, which allows for the ADC to reset rather than to saturate, thus producing modulo or folded samples. We discuss a recovery guarantee akin to Shannon’s sampling theorem which, remarkably, is independent of the maximum recordable ADC voltage. Our theory is complemented with a stable recovery algorithm. Moving further, we reinterpret the unlimited sensing framework as a generalized linear model and discuss the recovery of structured signals such as continuous-time sparse signals. This new sensing paradigm that is based on a co-design of hardware and algorithms leads to several interesting future research directions. On the theoretical front, a fundamental interplay of sampling theory and inverse problems raises new standalone questions. On the practical front, the benefits of a new way to sense the world (without dynamic range limitations) are clearly visible. We conclude this talk with a discussion on future directions and relevant applications.

Room

02.12.020

Thu, 17.10.2019

14:00 - 15:30

Speaker

Radha Ramakrishnan (IIT Madras)

Title

Multipliers for the Fourier transform

Abstract

The talk will be an overview of Prof. Ramakrishnan's interests in harmonic analysis.

Room

02.12.020

Tu, 22.10.2019

10:30 - 12:00

Speaker

Kathlén Kohn (KTH, Stockholm)

Title

The geometry of neural networks

Abstract

A fundamental goal in the theory of deep learning is to explain why the optimization of the loss function of a neural network does not seem to be affected by the presence of non-global local minima. Even in the case of linear networks, the existing literature paints a purely analytical picture of the loss, and provides no explanation as to why such architectures exhibit no bad local minima. We explain the intrinsic geometric reasons for this behavior of linear networks. For neural networks in general, we discuss the neuromanifold, i.e., the space of functions parameterized by a network with a fixed architecture. For instance, the neuromanifold of a linear network is a determinantal variety, a classical object of study in algebraic geometry. We introduce a natural distinction between pure critical points, which only depend on the neuromanifold, and spurious critical points, which arise from the parameterization. This talk is based on joint work with Matthew Trager.

Room

02.12.020

Tu, 29.10.2019

10:30 - 12:00

Speaker

Oleh Melnyk (TUM)

Title

Angular Synchronization and Ptychography

Abstract

The problem of angular synchronization naturally arises in the recovery of phaseless measurements, clock synchronization and computer vision. It requires the reconstruction of the vector of angles from their pairwise differences. As reconstruction is an NP hard problem, two common relaxations are used instead: semi-definite problem and eigenvector-based. We compare available recovery guarantees and present our new stronger bounds. On the other hand, Ptychography is a method of imaging, popular in a synchrotron community. It is based on illumination of one small region of the object at a time. Data from many overlapping regions is collected and then used for reconstruction of an object. We introduce a new algorithm called Div&Sync, which is a flexible and fast method for the recovery of an object. Based on joint work with Felix Krahmer and Frank Filbir.

Room

02.12.020

Tu, 05.11.2019

14:00 - 15:30

Speaker

Bernhard Schmitzer (TUM)

Title

Semi-discrete unbalanced optimal transport and quantization

Abstract

Semi-discrete optimal transport between a discrete source and a continuous target has intriguing geometric properties and applications in modelling and numerical methods. Unbalanced transport, which allows the comparison of measures with unequal mass, has recently been studied in great detail by various authors. In this talk we consider the combination of both concepts. The tessellation structure of semi-discrete transport survives and there is an interplay between the length scales of the discrete source and unbalanced transport which leads to qualitatively new regimes in the crystallization limit. Based on joint work with David P. Bourne and Benedikt Wirth.

Room

02.06.011

Tu, 19.11.2019

10:30 - 12:30

Speaker

Mauro Bonafini (TUM)

Title

A variational approximation scheme for hyperbolic obstacle problems

Abstract

We consider an obstacle problem for (possibly non-local) wave equations, and we prove existence of weak solutions through a convex minimization approach based on a time discrete approximation scheme.

Room

03.04.011

Tu, 26.11.2019

10:30 - 12:00

Speaker

Stefan Bamberger (TUM)

Title

The Restricted Isometry Property for Different Bases and Local Sparsity

Abstract

The restricted isometry property (RIP) of structured random matrices considers norm preservation of sparse vectors and has been one of the key problems studied in compressed sensing. It has been shown for matrices whose number of rows only exceeds the theoretical lower bound by logarithmic factors. In this talk, we consider existing approaches to generalize the RIP to vectors that are sparse in a different basis than the standard basis or vectors with limited numbers of non-zero entries within certain blocks. In both cases, we can reduce the number of logarithmic factors in the required number of rows by generalizing proof approaches for the classical RIP and dealing with the generalized conditions in an efficient way.

Room

03.04.011

Tu, 03.12.2019

10:30 - 12:00

Speaker

Marzieh Hasannas (TU Kaiserslautern)

Title

Frames and approximate operator representations

Abstract

In this talk, we will characterize the class of frames that can be represented as an orbit of a bounded operator. Only a few explicitly given frames are known to have this property. Motivated by this we provide various alternative ways of obtaining operator representations of frames, e.g., using multi-operator representations or only suborbit of a bounded operator. As the final step, we will consider approximate frame representations. This step turns out to remove all constraints appearing in the previously mentioned approaches.

Room

03.04.011

Tu, 10.12.2019

10:30 - 12:00

Speaker

Olga Graf (TUM)

Title

One-bit unlimited sampling

Abstract

The practical realization of Shannon’s sampling theorem via analog-to-digital converters (ADCs) suffers from a severe bottleneck: unlike sampling theorem, ADCs are limited in dynamic range and saturate whenever the signal amplitude exceeds the maximum recordable ADC voltage thus leading to a significant information loss. The recent theory of Unlimited Sampling circumvents this dynamic range problem and yields that a bandlimited function with high dynamic range can be recovered exactly from oversampled, low dynamic range samples obtained via modulo operation. In this talk, we will review key aspects of this new setup and also make a further step in practical direction by coupling modulo sampling with one-bit quantization. We will provide a constructive recovery algorithm for bandlimited signals from one-bit modulo samples and complement it with a bound on the reconstruction error.

Room

03.04.011

Tu, 17.12.2019

10:30 - 12:00

Speaker

Philippe Sünnen (TUM)

Title

Consensus-Based Optimization

Abstract

We present a particle system to minimize a function. The particles are driven by a system of coupled stochastic differential equations. We discuss the mean-field limit, implementation issues and applications..

Room

03.04.011

Tu, 14.01.2020

10:30 - 12:00

Speaker

Felix Krahmer (TUM)

Title

On the geometry of polytopes generated by heavy-tailed random vectors

Abstract

We study the geometry of centrally-symmetric random polytopes, generated by independent copies of a random vector taking values in . We show that under minimal assumptions on , for and with high probability, the polytope contains a deterministic set that is naturally associated with the random vector---namely, the polar of a certain floating body. This solves the long-standing question on whether such a random polytope contains a canonical body. Moreover, by identifying the floating bodies associated with various random vectors we recover the estimates that have been obtained previously, and thanks to the minimal assumptions on we derive estimates in cases that had been out of reach, involving random polytopes generated by heavy-tailed random vectors (eg, when is -stable or when has an unconditional structure). Finally, the structural results are used for the study of a fundamental question in compressive sensing---noise blind sparse recovery. This is joint work with Oliver Guédon, Christian Kümmerle, Shahar Mendelson and Holger Rauhut.

Room

03.04.011

Tu, 21.01.2020

10:30 - 12:00

Speaker

Martin Ehler (University of Vienna)

Title

Approximation of probability measures by curves of finite length

Abstract

We study the approximation of probability measures by measures with thinner support. In particular we use measures supported on the trajectories of curves. The distance between probability measures is quantified via the concept of L2-discrepancy. We then prove optimal approximation rates in terms of the curve's length. We also develop numerical schemes that achieve the optimal rates, and we provide several numerical examples. This is essentially joint work with A. Breger, J. Dick, M. Graef, C. Krattenthaler, S. Neymayer, and G. Steidl.

Room

03.04.011

Tu, 28.01.2020

10:30 - 12:00

Speaker

Carlos Améndola (TUM)

Title

Nonlinear Algebra of Low-Rank Matrix Completion

Abstract

In a matrix completion problem, one is presented with a subset of entries of a matrix and wishes to find values for the remaining entries so that the completed matrix has a particular property. For instance, one may want the completed matrix to have low rank or to be positive semidefinite. Such problems abound in application areas ranging from recommender systems (e.g. the "Netflix problem"), to rigidity theory, to compressed sensing, to maximum likelihood estimation for graphical models. Matrix completion problems also motivate many questions that can be considered fundamental within algebraic geometry. Studying low-rank matrix completion motivates the question: which coordinate projections of a given determinantal variety are dominant? What changes when one restricts to the real part of this determinantal variety? This talk will give an overview of the algebraic and geometric perspective and present open problems.