Optimal transport induces a geometrically intuitive metric on the space of probability measures and is a powerful tool for image and data analysis. With the evolution of efficient numerical methods it is becoming increasingly popular. However, in many models the assumption that all measures have unit mass and that mass is exactly preserved locally are too restrictive, for instance in biochemical growth processes. Hence, in recent years, `unbalanced' transport problems, that allow creation or annihilation of mass during transport, have received increased attention. In this talk we present several formulations for such problems, efficient numerical methods and illustrate applications and advantages of unbalanced metrics.

The Convex Geometry of Blind Deconvolution (and beyond)

Abstract

Blind deconvolution problems are ubiquitous in many areas such as imaging and communications and have been the object of study for several decades. Recently, motivated by the theory of compressed sensing, a new viewpoint has been introduced, in particular for applications in wireless communications, where a signal is transmitted through an unknown channel. Namely, the idea is to randomly embed the signal into a higher dimensional space before transmission and use the resulting redundancy for recovery. The first approach, proposed for example by Ahmed, Recht, and Romberg, was to employ convex optimization in the space of lifted matrix representations, but subsequently, many more efficient algorithms have been proposed and analyzed. The difficulty in the analysis is that recovery guarantees can only be expected for signals satisfying a certain incoherence constraints, which are hard to incoporate in some of the most powerful analysis approaches, for example those based on the restricted isometry property. For this reason most works on this topic use the golfing scheme by David Gross, which has the disadvantage that the resulting bounds often exhibit seemingly suboptimal error bounds and, furthermore, the results sometimes also exhibit proof artifacts. In this talk, we introduce a new analysis of the randomized blind deconvolution problem based on Mendelson’s small ball method, which gives rise to near-optimal error bounds for noise levels considerably larger than those covered by previous works. If time permits, we will also discuss how these ideas carry over to the Matrix Completion Problem. This is joint work with Felix Krahmer.

Room

03.10.011

Mo, 22.10.2018

14:00 - 15:30

Speaker

Robert Lung

Title

Approximation of noisy data matrices

Abstract

In situations where the acquisition of a full data set is infeasible it is natural to look for sampling procedures that produce a sufficiently informative subset of indices with high probability. In this presentation we assume that some information about the noisy data is available a priori (or can be obtained cheaply) and show that in such cases, under mild assumptions on the data set, it is possible to construct sampling procedures that (i) are based on the magnitude of the entries and yield sparse approximations of the data matrix with guaranteed error bounds or (ii) permit exact matrix completion from incomplete observations without the usual incoherence assumption. Our focus will be mainly on the latter where the sampling depends on the leverage scores of the data matrix. It will be outlined how those can be estimated from the data in an efficient way.

Room

02.10.011

Mo, 29.10.2018

14:00 - 15:30

Speaker

Florian Drechsler

Title

Discrete Gabor systems using special functions and their innate translations

Abstract

We present various new Gabor frames based on families of special functions, using certain (hypergroup) translations that arise from product formulas for these special functions. Our two main cases of interest are spherical Bessel functions and prolate spheroidal wave functions, also known as Slepian functions. In each case, we examine the reconstruction properties of these frames, and interpret the meaning of the Gabor frame coefficients.

Room

02.10.011

Mo, 5.11.2018

14:00 - 15:30

Speaker

Gianluca Orlando

Title

Fatigue effects in elastic materials with variational damage models

Abstract

In this talk I will present an existence result concerning quasistatic evolutions for a family of gradient damage models which take into account fatigue, that is the process of weakening in a material due to repeated applied loads. The main feature of these models is the fact that damage is favoured in regions where the cumulation of the elastic strain (or other relevant variables, depending on the model) is higher. The existence of a quasistatic evolution is proven via a vanishing viscosity approach based on two steps: first let the time-step of the time-discretisation and later the viscosity parameter go to zero. As the time-step goes to zero, one finds approximate viscous evolutions; then, as the viscosity parameter goes to zero, one finds a rescaled approximate evolution satisfying an energy-dissipation balance. The result is based on a work in collaboration with Roberto Alessi and Vito Crismale.

Room

02.10.011

Mo, 12.11.2018

14:00 - 15:30

Speaker

Felix Voigtländer

Title

Understanding sparsity properties of frames using function spaces

Abstract

We present a systematic approach towards understanding the sparsity properties of different frame constructions like Gabor systems, wavelets, shearlets, and curvelets. We use the following terminology: Analysis sparsity means that the frame coefficients are sparse (in an \ell^p sense), while synthesis sparsity means that the function can be written as a linear combination of the frame elements using sparse coefficients. While these two notions are completely distinct for general frames, we show that if the frame in question is sufficiently nice, then both forms of sparsity of a function are equivalent to membership of the function in a certain decomposition space. These decomposition spaces are a common generalization of Besov spaces and modulation spaces. While Besov spaces can be defined using a dyadic partition of unity on the Fourier domain, modulation spaces employ a uniform partition of unity, and general decomposition spaces use an (almost) arbitrary partition of unity on the Fourier domain. To each decomposition space, there is an associated frame construction: Given a generator, the resulting frame consists of certain translated, modulated and dilated versions of the generator. These are chosen so that the frequency concentration of the frame is similar to the frequency partition of the decomposition space. For instance, Besov spaces yield wavelet systems, while modulation spaces yield Gabor systems. We give conditions on the (possibly compactly supported!) generator of the frame which ensure that analysis sparsity and synthesis sparsity of a function are both equivalent to membership of the function in the decomposition space.

Room

02.10.011

Mo, 19.11.2018

14:00 - 15:30

Speaker

Toni Volkmer

Title

High-dimensional approximation and sparse FFT using (multiple) rank-1 lattices

Abstract

We consider the approximate reconstruction of a high-dimensional (e.g. d=10) periodic function from samples using trigonometric polynomials. As sampling schemes, we use rank-1 lattices, which can be constructed by a component-by-component approach when the locations of the approximately largest Fourier coefficients are known. With the help of a single one-dimensional fast Fourier transform (FFT), we are able to compute the Fourier coefficients, also in the high-dimensional case. For functions from Sobolev Hilbert spaces of generalized mixed smoothness, error estimates are presented where the sampling rates are best possible up to logarithmic factors. We give numerical results which confirm our theoretical estimates. Additionally, we discuss an approach where we use multiple instances of rank-1 lattices. This allows for efficient construction algorithms and we obtain improved error estimates where the sampling rates are optimal up to a small constant offset in the exponent. In particular, we consider the case where we do not know the locations of important Fourier coefficients. Here, we present a method which approximately reconstructs high-dimensional sparse periodic signals in a dimension-incremental way based on projections. The sampling nodes are adaptively chosen (multiple) rank-1 lattices and we use 1-dimensional FFTs for the computations. This is based on joint work with Glenn Byrenheid, Lutz Kämmerer, Daniel Potts, and Tino Ullrich.

Room

02.10.011

Mo, 26.11.2018

14:00 - 15:30

Speaker

Arseniy Tsipenyuk

Title

Variational Approach to Fourier Phase Retrieval

Abstract

This talk will discuss infinite-dimensional Fourier phase retrieval problem motivated by applications in X-ray crystallography. Assuming prior knowledge on the object (such as positivity or support), we reformulate the Error-Reduction algorithm as a discretized gradient flow (without the need to explicitly impose object space constraints), and show that the corresponding non-linear equation posesses global weak solutions. We use the gradient flow approach to analyze fixed point stability of the Error-Reduction algorithm and outline connections of this approach to the state-of-the-art algorithms. Joint work with Gero Friesecke.

Room

02.10.011

Mo, 3.12.2018

14:00 - 15:30

Speaker

Timo Klock

Title

Adaptively estimating nonlinear single index models with monotonic link functions

Abstract

The single index model (SIM) is a popular tool for modeling data where the output depends on the features through a linear 1D projection. If data follows this model, efficient estimation at 1D minimax rates is possible. However, the model space is restricted by the assumed linearity. In this talk we introduce a generalized SIM that allows for projections onto 1D manifolds. We propose an estimator based on local linear regression, where the localization happens in the output domain instead of in the feature domain. Finally, we present theoretical guarantees and numerical studies on real data sets to support the usefulness of a nonlinear SIM.

Room

02.10.011

Mo, 10.12.2018

14:00 - 15:30

Speaker

Christian Kümmerle

Title

Denoising and Completion of Structured Low-Rank Matrices via Iteratively Reweighted Least Squares

Abstract

In this talk, we propose and analyze a new Iteratively Reweighted Least Squares (IRLS) algorithm for the problems of completion and approximation of a matrix by low-rank matrices that are low-rank and also linearly structured. For the particular case of Hankel or Toeplitz matrix completion, which has applications for the super resolution or harmonic retrieval problem, we establish local convergence of the algorithm with a quadratic rate of convergence, under appropriate assumptions on the sample complexity. These assumptions on the sample complexity match the weakest ones available in the literature. At the same time, we provide numerical experiments demonstrating that our approach beats the state-of-the-art in terms of data efficiency. This is based on joint work with Claudio Mayrink Verdun.

Room

02.10.011

Mo, 17.12.2018

14:00 - 15:30

Speaker

Riccardo Scala

Title

The relaxed area functional and related Plateau problems

Abstract

Starting from old results on the analysis of polyconvex functional with linear growth, (specifically from a paper by Acerbi-Dal Maso, based in turn on some conjectures of E. De Giorgi), we summarize the history of the relaxed area functional. We also discuss how to solve a conjecture on the exact value of the area functional on some piecewise constant functions, and how to extend it to several other cases. In the second part of the talk we discuss open problems related to the area functional and specifically we present some Plateau type problems arising from this analysis.

Room

02.10.011

Mo, 7.01.2019

14:00 - 15:30

Speaker

Frank Filbir

Title

Product Formulas, Geometric Analysis, and Hypergroups

Room

02.10.011

Mo, 14.01.2019

14:00 - 15:30

Speaker

Johannes Maly

Title

Joint Recovery from One-Bit Measurements via Hard-Thresholding

Abstract

In this talk we will discuss the interplay between distributed compressed sensing and one-bit quantization. We show that a single hard-thresholding step well approximates ensembles of jointly s-sparse signals from O(s) one-bit Gaussian measurements per signal if the number of signals is sufficiently large.

Room

02.10.011

Mo, 21.01.2019

14:00 - 15:30

Speaker

Oleh Melnyk

Title

Phase Retrieval from Local Correlation Measurements with Fixed Shift Length

Abstract

We consider the natural extension of phase retrieval with local correlation measurements with shifts of length one to any fixed length size. As a result, we provide algorithms and recovery guaranties for extended model, as well as suitable measurements constructions.

Room

02.10.011

Mo, 28.01.2019

14:00 - 15:30

Speaker

Stefan Bamberger

Title

Generic Chaining Applied to the RIP of Structured Random Matrices

Abstract

The approaches by Haviv/Regev and Rudelson/Vershynin show a restricted isometry property of bounded orthonormal systems. Both of these approaches rely on generic chaining. This technique can be shown to be optimal up to constants. However, when it is applied to specific situations, often non-sharp estimates are used that lead to logarithmic factors in the overall result. Our goal is to analyze such estimates in the aforementioned proofs and develop approaches that can improve logarithmic factors in the number of required rows of the matrices.

Room

02.10.011

Mo, 04.02.2019

14:00 - 15:30

Speaker

Bernahrd Schmitzer

Title

Unbalanced Optimal Transport

Abstract

Optimal transport induces a geometrically intuitive metric on the space of probability measures and is a powerful tool for image and data analysis. With the evolution of efficient numerical methods it is becoming increasingly popular. However, in many models the assumption that all measures have unit mass and that mass is exactly preserved locally are too restrictive, for instance in biochemical growth processes. Hence, in recent years, `unbalanced' transport problems, that allow creation or annihilation of mass during transport, have received increased attention. In this talk we present several formulations for such problems, efficient numerical methods and illustrate applications and advantages of unbalanced metrics.