Structured low-rank approximation approach to sum-of-exponentials

Markovsky, I. (Speaker)

Activity: Talk or presentationTalk at an external academic organisation


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.
Period14 Jun 201519 Jun 2015
Event titleSparse modelling and multi-exponential analysis, Dagstuhl Semiinar
Event typeSeminar
LocationDagstuhl, Germany