2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Collection 2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Organizer(s) van der Hoeven, Joris ; Giesbrecht, Mark ; Koiran, Pascal ; Villard, Gilles
Date(s) 25/09/2023 - 29/09/2023
linked URL https://indico.math.cnrs.fr/event/8113/
16 17

Sparse interpolation and Exponential analysis going hand in hand

By Annie Cuyt

We discuss how sparse interpolation in computer algebra and exponential analysis in digital signal processing can cross-fertilize and lead to new results. The Nyquist constraint is the digital signal processing equivalent of stating that the argument of a complex exponential exp(φ∆) with φ ∈ C and ∆ ∈ R+ can only be retrieved uniquely under the condition that |=(φ)|∆ < π. It governs signal processing since the beginning of the 20-th century. In the past two decades this constraint was first broken with the use of randomly collected signal samples and later for use with uniform samples. The latter method closely relates to the original version of the exponential data fitting algorithm published in 1795 by the French mathematician de Prony, which is often cited in sparse interpolation research. In engineering applications it is mostly implemented using a structured generalized eigenvalue approach. Besides avoiding the Nyquist constraint, the new result in also solves a number of remaining open problems in exponential analysis, which we plan to discuss. In the identification, from given values fk ∈ C, of the nonlinear parameters φ1, . . . , φn ∈ C, the linear coefficients α1, . . . , αn ∈ C and the sparsity n ∈ N in the inverse problem n∑ j=1 αj exp(φj k∆) = fk, k = 0, . . . , 2n − 1, . . . fk ∈ C, ∆ ∈ R+, (1) several cases are considered to be hard [6, 1]: When some of the φj cluster, the identification and separation of these clustered φj becomes numerically ill-conditioned. We show how the problem may be reconditioned. Retrieval of the correct value of n is difficult, and more so in case of clustered φj and noisy samples fk. Here, decimation of the data offers a way to obtain a reliable estimate of n automatically. Such decimation allows to divide and conquer the inverse problem statement. The smaller subproblems are largely independent and can be solved in parallel, leading to an improved complexity and efficiency. At the same time, the sub-Nyquist Prony method proves to be robust with respect to outliers in the data. Making use of some approximation theory results [9, 10, Kn.Cu:rob:23], we can also validate the computation of the φj and αj . The Nyquist constraint effectively restricts the bandwidth of the =(φj ). Therefore, avoiding the constraint offers so-called superresolution, or the possibility to unearth higher frequency components in the samples. All of the above can be generalized in several ways, to the use of more functions besides the exponential on the one hand, and to the solution of multdimensional inverse problems as in on the other.

Information about the video

  • Date of publication 29/09/2023
  • Institution IHP
  • Licence CC BY-NC-ND
  • Language English
  • Format MP4

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback