The Localization Problem and Sparse Sets

A core problem in the information age is to represent data in a way such that its characteristic features are revealed. In real world applications such as wireless communication and optics however the capacities to measure these representations are limited and information is only available on a certain domain of interest. One can then ask how to infer a signal from its limited measurements. A rigorous mathematical formulation then gives the localization problem which, in simplified terms, can be formulated as follows: Given a function from a special class of functions, how well can the energy respectively the mass of the function be concentrated on certain subsets of the domain of definition? Despite the readily understandable formulation there exist only few exact solutions to the problem for certain special function classes and subsets. It is the main goal of this project to establish new estimates that depend on easily computable values and that provide a good approximation of the actual solution. In particular, we aim to explain the effect that, in many cases, functions can only be poorly localized on sparse sets, i.e., sets that are locally of small size. The localization problem is important in many fields of mathematics for example in signal processing. There, one is interested in determining how much information on a function is needed in order to perfectly reconstruct it. This project will make use of the so-called large sieve method which originates from analytic number theory and is widely utilized in that field. The approach of applying the large sieve to study localization was first used in a paper by Donoho and Logan in the case of band-limited functions on the real line. Within LOSSLEsS we hypothesize that these ideas can be transferred to various other function spaces. For example we intend to study localization of the short-time Fourier transform and functions defined on the 3- dimensional sphere. These functions play an important role in different applications, for example in acoustics. If the project is successful, it would provide researchers with novel upper bounds on the localization problem on the considered function spaces without the need of elaborate calculations or numerical approximations.

A core problem in the current information age is to represent data in a way such that its characteristic features are revealed. In real world applications such as wireless communication and optics however the capacities to measure these representations are limited and information is only available on a certain domain of interest. It was the goal of this project to apply Donoho-Logan's large sieve in order to derive estimates which allow to infer properties of the original signal (or even its complete reconstruction). In mathematical terms we were concerned with quantitative estimates of the localization problem which, in simplified terms, can be formulated as follows: Given an element of a special class of functions, how well can the energy (respectively the mass) of the function be concentrated on certain subsets of the domain of definition? Despite the readily understandable formulation there existed only a few exact solutions to the problem for certain special function classes and subsets. Donoho-Logan's large sieve allowed us in this project to show quantitative upper and lower bounds for example for the localization problem of the short-time Fourier transform or for band-limited functions on the 3-dimensional sphere. The latter result could even be extended to a more general class of algebraic objects. The above mentioned function classes play an important role in a multitude of applications in signal processing, for example in acoustics. Upon closer inspection, our results theoretically confirm the observation that in many cases functions cannot be well-localized on sparse sets, i.e. on sets that are locally of small size. One can interpret this as yet another manifestation of the famous uncertainty principle. With the completion of this project, there are now quantitative estimates to the solution of the localization problem available for various function spaces without having to resort to an elaborate search for exact solutions or a numerical approximation. It moreover turned out that this method is readily transferable and applicable in many other contexts. In addition, we also showed several results in directions that were not originally included in the project proposal. Here, two contributions should particularly be mentioned: first we investigated the concentration of the short-time Fourier transform on curves in space and second we showed the existence of a Nyquist density for a class of polyanalytic wavelets which is a partial solution to a longstanding open problem in wavelet theory.