Dagstuhl-Seminar 15251
Sparse Modelling and Multi-exponential Analysis
( 14. Jun – 19. Jun, 2015 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/15251
Organisatoren
- Annie Cuyt (University of Antwerp, BE)
- George Labahn (University of Waterloo, CA)
- Avraham Sidi (Technion - Haifa, IL)
Koordinator
- Wen-shin Lee (University of Antwerp, BE)
Kontakt
- Susanne Bach-Bernhard (für administrative Fragen)
Programm
The research fields of harmonic analysis, approximation theory and computer algebra are seemingly different domains and are studied by seemingly separated research communities. However, all of these are connected to each other in many ways.
The connection between harmonic analysis and approximation theory is not accidental: several constructions among which wavelets and Fourier series, provide major insights into central problems in approximation theory. And the intimate connection between approximation theory and computer algebra exists even longer: polynomial interpolation is a long-studied and important problem in both symbolic and numeric computing, in the former to counter expression swell and in the latter to construct a simple data model.
A common underlying problem statement in many applications is that of determining the number of components, and for each component the value of the frequency, damping factor, amplitude and phase in a multi-exponential model. It occurs, for instance, in magnetic resonance and infrared spectroscopy, vibration analysis, seismic data analysis, electronic odour recognition, keystroke recognition, nuclear science, music signal processing, transient detection, motor fault diagnosis, electrophysiology, drug clearance monitoring and glucose tolerance testing, to name just a few.
The general technique of multi-exponential modeling is closely related to what is commonly known as the Padé-Laplace method in approximation theory, and the technique of sparse interpolation in the field of computer algebra. The problem statement is also solved using a stochastic perturbation method in harmonic analysis. The problem of multi-exponential modeling is an inverse problem and therefore may be severely ill-posed, depending on the relative location of the frequencies and phases. Besides the reliability of the estimated parameters, the sparsity of the multi-exponential representation has become important. A representation is called sparse if it is a combination of only a few elements instead of all available generating elements. In sparse interpolation, the aim is to determine all the parameters from only a small amount of data samples, and with a complexity proportional to the number of terms in the representation.
Despite the close connections between these fields, there is a clear lack of communication in the scientific literature. The aim of this seminar is to bring researchers together from the three mentioned fields, with scientists from the varied application domains.
The seminar brought together a number of researchers from polynomial interpolation, rational approximation and exponential analysis. The five day seminar centered around talks on Exponential Analysis (Day 2), Rational Approximation (Day 3) and Sparse Interpolation (Day 4). Applications were grouped on Day 1 in order to challenge the participants to discuss them further while related topics, mainly from Numerical Linear Algebra, were scheduled on Day 5.
The seminar itself started with a talk by Cuyt and Lee pointing out the considerable intersection of the three main themes, particularly as they all strongly overlap. In order to reach out to industry and connect the scientific research to the industrial needs, several participants working at industrial or real-life applications were invited for a presentation on the first day of the seminar. Then interaction about these topics would occur naturally throughout the week. We mention talks on Mobile sampling and sensor networks (Karlheinz Gröchenig), High-speed fluorescence lifetime imaging (David Li), The estimation of variable star periods (Daniel Lichtblau) and Imaging of structured arrays (Adhemar Bultheel).
In the past the three communities have mostly been following distinct paths of research and methods for computation. One of the highlights of the seminar was the realization of significant commonalities between the communities, something nicely pointed out in the talk of Roche. Prony's method takes center stage in this case, with its origin in 1795 being used to solve problems in exponential analysis. Prony's method appeared much later in the case of sparse polynomial interpolation with it's use by Blahout, Ben-or/Tiwari, and Giesbrecht/Labahn/Lee. Prony's method takes samples at multiples of a common point to determine the support and then makes use of separate Hankel methods for determining the individual coefficients or weights of the expression.
Numerical conditioning was a significant issue in many talks at the seminar. Beckermann and later Matos looked at numerical conditioning of Padé and rational approximation problems. In the former case Beckermann used the close relationship of Padé approximation to Prony's method to point out that the latter is, for the most part, a provably ill-conditioned problem. Still there were a number of approaches in both areas which attempted to address this conditioning issue. In the case of numerical computation of sparse polynomial interpolants, use is made of randomization to produce a better conditioning of the problem, primarily by separating the roots appearing in Prony's problem. A similar idea also appears in exponential analysis making use of the notion of stride length. In both cases the object is to spread out the roots which arise in Prony's method.
Rather than spreading out the roots one can instead spread out the coefficients of a sparse polynomial/exponential expression for improving numerical performance. Sparse interpolation does this by making use of the concept of diversification where the coefficients are spread out multiplying evaluation points using a random multiplier. A corresponding concept in exponential analysis is the use of shifted samples which is useful to address the problem of anti-aliasing.
Sparse interpolation also makes use of the concept of small primes sparse interpolation where exponents are reduced modulo a small prime. This recovers the exponents modulo the small prime. Doing this for a number of small primes (which can be done in parallel) allows one to reconstruct the true exponents. Of course one encounters the problem of collisions and inadvertant combinations of exponents. It was noticed at the seminar that exponential analysis has a corresponding technique which made use of sub-sampling. Collisions in this case correspond to aliasing. Again the different communities reported on their methods for overcoming such collisions/aliasing problems.
Researchers at the seminar also showed interest in multivariate Prony methods. In the case of sparse interpolation one encounters Zippel's method while in exponential analysis there are projection methods. In these cases one attempts recursive methods for estimating the support of the underlying multivariable expression. In the case of multivariate polynomial interpolation a second approach is to convert the multivariate problem into a univariate problem by making use of randomized Kronecker substitution. Exponential sums takes a similar approach using random lattice projection.
While there were strong commonalities between the main research areas, there were also some strong differences between the topics noted at the seminar. The most telling of these differences was the analysis of exponential sums which have polynomial, rather than constant coefficients. Such expressions appear naturally when modeling solutions of linear differential equations where the associated polynomial has repeated roots. Of course such problems have considerable numerical issues when the roots of the associated polynomial are close but not numerically equal. Sidi and Batenkov both pointed out the importance and difficulties when dealing with such problems.
The seminar was also important for illustrating the applications of the three research areas. In many cases the applications involved the need to only work with sums having a small sparse support rather than with the complete set of possible nonzero elements. Methods from the multivariate Prony problem were exploited by Collowald and Hubert to determine new cubature formulas invariant to some specific finite groups action. Markovsky showed the similarities to the exponential sum problems with the notion of low rank approximation of structured matrices. Software was also discussed. Numerical analysis of errors on experimental runs also brought up the issue of the type of random distributions used when simulating errors for the experiments.
Creative Commons BY 3.0 Unported license
Annie Cuyt and George Labahn and Avraham Sidi and Wen-shin Lee
- John Abbott (University of Genova, IT) [dblp]
- Fredrik Andersson (Lund University, SE) [dblp]
- Andrew Arnold (University of Waterloo, CA) [dblp]
- Dmitry Batenkov (Technion - Haifa, IL) [dblp]
- Bernhard Beckermann (University of Lille, FR) [dblp]
- Matteo Briani (University of Antwerp, BE) [dblp]
- Adhemar Bultheel (KU Leuven, BE) [dblp]
- Mathieu Collowald (INRIA Sophia Antipolis - Méditerranée, FR)
- Annie Cuyt (University of Antwerp, BE) [dblp]
- Stefano de Marchi (University of Padova, IT) [dblp]
- Pier Luigi Dragotti (Imperial College London, GB) [dblp]
- Jürgen Gerhard (Maplesoft - Waterloo, CA) [dblp]
- Mark Giesbrecht (University of Waterloo, CA) [dblp]
- Karlheinz Gröchenig (Universität Wien, AT) [dblp]
- Lasse Holmström (University of Oulu, FI) [dblp]
- Evelyne Hubert (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
- Erich Kaltofen (North Carolina State University - Raleigh, US) [dblp]
- Stefan Kunis (Universität Osnabrück, DE) [dblp]
- George Labahn (University of Waterloo, CA) [dblp]
- Wen-shin Lee (University of Antwerp, BE) [dblp]
- David Levin (Tel Aviv University, IL) [dblp]
- David Li (The University of Strathclyde - Glasgow, GB) [dblp]
- Daniel Lichtblau (Wolfram Research - Champaign, US) [dblp]
- Ivan Markovsky (Free University of Brussels, BE) [dblp]
- Ana C. Matos (Lille I University, FR) [dblp]
- Katharine M. Mullen (UCLA, US) [dblp]
- Luca Perotti (Texas Southern Unversity - Houston, US) [dblp]
- Thomas Peter (Universität Osnabrück, DE) [dblp]
- Gerlind Plonka-Hoch (Universität Göttingen, DE) [dblp]
- Daniel Potts (TU Chemnitz, DE) [dblp]
- Daniel Roche (U.S. Naval Academy - Annapolis, US) [dblp]
- Avraham Sidi (Technion - Haifa, IL)
- Manfred Tasche (Universität Rostock, DE) [dblp]
- Akira Terui (University of Tsukuba, JP) [dblp]
- Konstantin Usevich (GRIPSA Lab - Saint Martin d'Hères, FR) [dblp]
- Ulrich von der Ohe (Universität Osnabrück, DE)
- Katrin Wannenwetsch (Universität Göttingen, DE) [dblp]
- Stephen M. Watt (University of Western Ontario - London, CA) [dblp]
- Marius Wischerhoff (Universität Göttingen, DE)
- Yosef Yomdin (Weizmann Institute - Rehovot, IL) [dblp]
- Lihong Zhi (MMRC - Beijing, CN) [dblp]
Verwandte Seminare
Klassifikation
- modelling / simulation
Schlagworte
- sparse interpolation
- exponential analysis
- signal processing
