From Sparse Interpolation to Signal Processing: New Synergies

We address the problem of detecting the number of complex exponentials and estimating their parameters from a noisy signal using the Matrix Pencil (MP) method. We introduce the MP modes and present their informative spectral structure. We show theoretically that these modes can be divided into signal and noise modes, where the signal modes exhibit a perturbed Vandermonde structure. Leveraging this structure, we proposed a new MP algorithm, termed the SAMP algorithm, which has two novel components. First, we present a new and robust model order detection with theoretical guarantees. Second, we present an efficient estimation of signal amplitudes. We show empirically that the SAMP algorithm significantly outperforms the standard MP method, particularly in challenging conditions with closely spaced frequencies and low Signal-to-Noise Ratio (SNR) values. Additionally, compared with prevalent information based criteria, we show that SAMP is more computationally efficient and insensitive to noise distribution.

The task of separating a superposition of signals into its individual components is a common challenge encountered in various signal processing applications, especially in domains such as audio and radar signals. A previous paper by Chui and Mhaskar [1] proposes a method called Signal Separation Operator (SSO) to find the instantaneous frequencies and amplitudes of such superpositions where both of these change continuously and slowly over time. In this talk, we amplify and modify this method in order to separate linear chirp signals in the presence of crossovers, a very low SNR, and discontinuities.

The main problem of signal separation is to determine the locations ${\omega }_k$ of a signal of the form $\mu (t)={\sum }_{k=1}^K{a}_k{\delta }_{{\omega }_k}(t)$, given observations

where the $\epsilon (j)$’s are independent samples from some noise distribution. A key piece of information is the minimal separation among the ${\omega }_k$’s, which dictates the complexity of a model necessary to recuperate the locations to a given accuracy. As this minimal separation tends to zero, we end up in a regime known as super-resolution, which poses its own challenges.

In this work we examine a generalization of the signal separation and super-resolution settings by considering a measure of the form

where ${\mu }_k$’s are each measures on some unknown domain. By allowing the constituent measures themselves to be supported on some dense set, our problem of interest incorporates both signal separation and super-resolution as particular cases. We give theory and a method to estimate the supports of the ${\mu }_k$’s given only finitely many samples from $\mu$.

One application of this work lies in machine learning, where we have developed an algorithm for data classification in the active learning paradigm. Therefore, we are able to view signal separation, super-resolution, and machine learning classification problems under a unified umbrella.

In this talk, we present algorithms for the approximation of multivariate functions. We start with the approximation by trigonometric polynomials based on sampling of multivariate functions on rank-1 lattices. To this end, we study the approximation of functions in periodic Sobolev spaces of dominating mixed smoothness. The proposed algorithm based mainly on a one-dimensional fast Fourier transform, and the arithmetic complexity of the algorithm depends only on the cardinality of the support of the trigonometric polynomial in the frequency domain. After a detailed introduction we will focus on the following questions in more detail.

• $\mathrm{■}$

  We discuss methods where the support of the trigonometric polynomial is unknown.

• $\mathrm{■}$

  We describes an extension of approximation methods for nonperiodic functions via a multivariate change of variables.

• $\mathrm{■}$

  Based on these methods we develop algorithms for discrete operator learning.

This talk deals with the approximation error of trigonometric interpolation for multivariate functions of bounded variation in the sense of Hardy-Krause. We propose interpolation operators related to both the tensor product and sparse grids on the multivariate torus. For these interpolation processes, we investigate the corresponding error estimates in the Lp norm for the class of functions under consideration. In addition, we compare the accuracy with the cardinality of these grids in both approaches. This is joint work with E. Semenova (Institute of Mathematics, Ukrainian Academy of Sciences, Kiev and University of Lübeck).

Continuous, non-invasive monitoring of cerebral blood flow (CBF) is critically important for managing patients in intensive care, particularly neonates and individuals suffering from stroke or traumatic brain injury. Traditional imaging modalities such as MRI or CT remain impractical for bedside or long-term monitoring due to their cost, size, and the need for patient transport. Dr Li’s team has developed a compact, low-cost CBF sensing platform based on near-infrared diffuse correlation spectroscopy (DCS), integrated with advanced single-photon avalanche diode (SPAD) sensors. This system offers high sensitivity to microvascular blood flow dynamics with minimal hardware complexity. While current single- or dual-channel systems can monitor CBF changes at discrete sites, the team’s vision is to extend this to a multi-channel platform capable of reconstructing three-dimensional images of cerebral perfusion in real time. However, this transition from localised sensing to volumetric imaging poses significant computational and mathematical challenges, especially in addressing the ill-posed inverse problem associated with reconstructing CBF maps from sparse, noisy data. In this presentation, Dr Li will first provide an overview of the physiological motivations for non-invasive, continuous CBF monitoring and outline the limitations of existing technologies. He will then introduce the principles behind DCS and SPAD-based detection, and share results from their current system, including real-time CBF signal recovery in human subjects. The core focus will be on their roadmap towards a multi-channel CBF tomography system, combining hardware innovation with advanced image reconstruction algorithms. The team is particularly keen to engage with mathematicians and computational scientists specialising in inverse problems, compressed sensing, and sparse sampling. Their aim is to identify robust, efficient reconstruction methods to deliver accurate 3D CBF distributions from a minimal number of optical channels, thereby reducing system cost, computational load, and design complexity. By the end of the session, they hope to stimulate interdisciplinary dialogue and explore collaborations to co-develop the next generation of portable, non-invasive cerebral imaging tools that could transform neurocritical care and neonatal monitoring.

The principle of confocal microscopy is presented. Included is the description of signal structure and challenges of signal analysis. A typical setup has been in practice for many years, however it has limitations for current requirements. We developed a new setup for a much faster and less complicated system which requires a different way of the analysis of the signals. First results are presented.

The study of historical watermarks plays a major role in provenance research to determine the date and origin of paper-based writing and art. One of the main watermark collections is the so-called Wasserzeichen-Informationssystem (WZIS) that gathers watermarks from rubbings, handtracings, radiography, and thermography. Since the WZIS consists of nearly as many classes as samples, the training of common deep learning architectures does not yield reliable classifiers. Moreover, digitization techniques like the nowadays employed thermography are highly unstandardized, giving the reason to develop classifies that are invariant under affine image transformations. Based on the so-called Radon cumulative distribution transform (R-CDT), we therefore propose two easy-to-compute feature extractors that facilitate image classification tasks especially in the small data regime and guarantee linear separability of image classes that emerge from affine transformations. Studying the proposed max- and mean-normalized R-CDT, we show robustness against non-affine image deformations. Furthermore, the separability properties of both extractors are stable provided the Wasserstein distance between the samples can be controlled. Our theoretical results are supported by numerical experiments and may pave the path towards computational filigranology.

Our main objective in this work is to demonstrate how orthogonal Sobolev polynomials emerge as a useful tool within the framework of spectral methods for boundary-value problems. The solution of a boundary-value problem for a stationary Schrödinger equation on the unit ball can be studied from a variational perspective. In this variational formulation, a Sobolev inner product naturally arises. As test functions, we consider the linear space of polynomials satisfying the boundary conditions on the sphere, and a basis of mutually orthogonal polynomials with respect to the Sobolev inner product is provided. The basis of the proposed method is provided in terms of spherical harmonics and univariate Sobolev orthogonal polynomials. The connection formula between these orthogonal Sobolev polynomials and classical orthogonal polynomials on the ball is established. Consequently, the Sobolev Fourier coefficients of a function satisfying the boundary value problem are recursively derived. Finally, numerical experiments were presented.

We present a measurement-based method for jointly estimating the element positions and mutual-coupling coefficients of uniform linear arrays (ULAs) directly from embedded-element radiation patterns. The problem is cast as a Prony model whose shared exponential bases encode the electrical spacing (frequency and element locations), while the model coefficients capture the mutual coupling. By applying multi-snapshot validated exponential analysis (VEXPA) to the noisy pattern samples, the common bases are retrieved with sufficient resilience to noise. The coefficients are then obtained from an overdetermined Vandermonde system that is nearly perfectly conditioned. The technique is demonstrated on two cases:

• $\mathrm{■}$

  Synthetic example – An 11-element dipole ULA spanning 800–1200 MHz, sampled at 51 frequencies, with added white Gaussian noise (SNR = 60 dB). Using 361 pattern samples, the base terms and coefficients are both recovered. The relative error of the coefficients is in the order of 10-5,

• $\mathrm{■}$

  Measured array – A 4-element dipole ULA measured from 2.8–3.2 GHz at nine frequencies (again 361 samples). Both the base terms and the coefficients were extracted, allowing the mutual coupling terms to be determined with sufficient accuracy.

In the first part of the talk, we investigate the recovery of nodes and amplitudes from noisy frequency samples in spike train signals, also known as the super-resolution (SR) problem. When the node separation falls below the Rayleigh limit, the problem becomes ill-conditioned. Admissible sampling rates, or decimation parameters, improve the conditioning of the SR problem, enabling more accurate recovery. We propose an efficient preprocessing method to identify the optimal sampling rate, significantly enhancing the performance of SR techniques.

For the second part of the talk, we study the spectral properties of infinitely smooth multivariate kernel matrices when the nodes form a single cluster. We show that the geometry of the nodes plays an important role in the scaling of the eigenvalues of these kernel matrices. For the multivariate Dirichlet kernel matrix, we establish a criterion for the sampling set ensuring precise scaling of eigenvalues. Additionally, we identify specific sampling sets that satisfy this criterion. Finally, we discuss the implications of these results for the problem of super-resolution, i.e. stable recovery of sparse measures from bandlimited Fourier measurements.

An estimation problem is a problem in which one infers or estimates a certain quantity or state based on uncertain information or observed data. Estimation problems play a crucial role across various disciplines, including statistics, machine learning, signal processing, and control theory. To solve estimation problems, numerical methods such as the gradient method or genetic algorithms are used. However, gradient methods may return a local solution, depending on the initial values, since they utilize local convergence properties. The genetic algorithm has some disadvantages, as it sometimes fails to properly solve the estimation problem due to phenomena such as initial convergence and hitchhiking. On the other hand, using minimax approximation together with Gröbner bases computation may avoid these phenomena, for this method evaluates values globally. In this presentation, we propose a method for solving estimation problems using minimax polynomials and Gröbner bases. We show an application of the proposed method for solving a speech direction estimation problem.

Prony’s method can be used for sparse interpolation over any ring: Given black box access to a polynomial with $t$ non-zero terms, its coefficients and exponents can be computed from evaluations on a geometric sequence of size $2t$. However, over exact rings such as the integers or finite fields, this algorithm is computationally expensive. Several techniques have been developed by the computer algebra community to speed up the algorithm. As a result, a sparse polynomial over the integers can be interpolated at a cost that is quasi-linear in the size of its sparse representation.

Efficient polynomial or integer multiplication is at the core of computer algebra and these problems received a lot of attention since the last past decades to reach quasi-linear time complexity. Nowadays, it is even possible to multiply polynomials with integer coefficients within a quasi-optimal complexity. Note that the latter result assumes that the bit-lengths of the coefficients must not vary too much, meaning that polynomials with very unbalanced coefficients are out of reach yet. In this talk, I will show how this problem of unbalanced integer polynomials multiplication is related to sparse polynomial interpolation. By using our recent technique on sparse interpolation for integer polynomial, we show how we can reach an almost quasi-optimal complexity for the multiplication problem. In particular, we will describe a new algorithm that enables the interpolation of sparse unbalanced polynomials in almost quasi-linear time.