MULAN: A Blind and Off-Grid Method for Multichannel Echo Retrieval

This paper addresses the general problem of blind echo retrieval, i.e., given M sensors measuring in the discrete-time domain M mixtures of K delayed and attenuated copies of an unknown source signal, can the echo locations and weights be recovered? This problem has broad applications in fields such as sonars, seismology, ultrasounds or room acoustics. It belongs to the broader class of blind channel identification problems, which have been intensively studied in signal processing. Existing methods in the literature proceed in two steps: (i) blind estimation of sparse discrete-time filters and (ii) echo information retrieval by peak-picking on filters. The precision of these methods is fundamentally limited by the rate at which the signals are sampled: estimated echo locations are necessary on-grid, and since true locations never match the sampling grid, the weight estimation precision is impacted. This is the so-called basis-mismatch problem in compressed sensing. We propose a radically different approach to the problem, building on the framework of finite-rate-of-innovation sampling. The approach operates directly in the parameter-space of echo locations and weights, and enables near-exact blind and off-grid echo retrieval from discrete-time measurements. It is shown to outperform conventional methods by several orders of magnitude in precision.

Rémi Gribonval, Helena Peic Tukuljac

2018

Uncertain Sampling with Certain Priors

Golnooshsadat Elhami

Sampling has always been at the heart of signal processing providing a bridge between the analogue world and discrete representations of it, as our ability to process data in continuous space is quite limited. Furthermore, sampling plays a key part in understanding how to efficiently capture, store and process signals. Shannon's sampling theorem states that if the original signal is known to have a limited bandwidth, we can retrieve the signal from uniformly-spaced samples, provided that the sampling rate is greater than twice the highest frequency in the signal. Here, we see two key attributes: prior knowledge on the original signal (limited bandwidth) and a constrained sampling setup (uniform samples at a particular rate). In this thesis, we make weaker assumptions on the sampling setup by assuming that some information, such as the sample positions, is lost. We show that under proper prior knowledge, we can reconstruct the signal from its samples uniquely or up to some equivalence class. We start by the problem of linear sampling of discrete signals, where the sample values are known, but their order is lost. In general, the original signal is impossible to retrieve from the samples, but we show that by taking out symmetry from the sampling vectors, we can reconstruct the signal uniquely. We provide an efficient algorithm to find the sample orders and thus reconstruct the original signal. We also study the problem of reconstructing a continuous signal from samples taken at unknown locations. The lost sample locations take away any hope of uniquely retrieving the signal without prior knowledge. We show that this problem is equivalent to reconstructing a composite of functions from uniformly spaced samples. Then we provide an efficient algorithm that can recover bandlimited signals warped by a linear function uniquely given enough sampling frequency. We then investigate a problem, dubbed shape from bandwidth, where we have uniform samples from a picture (projection) of an unknown surface that is painted with an unknown texture. The goal is to reconstruct the shape of the surface from these samples. We show that having prior knowledge of the texture bandwidth provides us with enough information to reconstruct the surface from its picture. We provide reconstruction algorithms for both orthogonal and central projections and provide equivalence classes of solutions in each case. Next, in two consecutive chapters, using techniques from geometrical signal processing, we offer new designs for 3-D barcodes, whose information can be retrieved from a single projection using penetrating waves from an unknown direction. Because of the unknown scan direction, the correct correspondence of the samples to the information bits in the barcodes is lost. In this case, we use the known shape of the barcode as prior knowledge to estimate the unknown scan direction from the samples, and then transform the reconstruction as a linear problem that can be solved efficiently. Finally, we cover the theory of coordinate difference matrices (CDMs): matrices that store mutual differences between coordinates of points (sensors, microphones, molecules, etc.) in space. We show how we can leverage specific properties of these matrices, such as their low rank, as prior knowledge in order to reconstruct the position of the points in space using CDMs. We use our reconstruction algorithm to solve many real-life signal processing problems.

EPFL2021

Adaptive frequency tracking and application to biomedical signals

Yann Prudat

The main information of a signal resides in its frequency, its amplitude (or its power) and in their temporal evolution. Thus, a great number of methods for instantaneous frequency estimation have been proposed in the literature. Most of these algorithms use an adaptive filter-based (notch or bandpass filter) structure. In many applications, the information of interest is present in more than one signal. However, to our knowledge no algorithm able to track the frequency on several signals has been presented in the literature. Usually, frequency components are estimated and extracted on each signal independently. Artifacts or noise relative to a specific signal can thus disturb the frequency estimation process. Moreover, low amplitude components present in every signal (but non dominant) will not be estimated. The objective in the first part of this thesis is to develop different methods able to extend existing frequency tracking algorithm in order to improve the quality of the estimate, in terms of estimation variance and robustness with respect to noise. The proposed methods can be applied to algorithms using adaptive filters for the frequency estimation. For the multi-signal frequency tracking extension, these methods use the redundancy of information present in the signals under study. A first approach uses a unique filter for every signal. A set of weights is computed, depending on a measure of the estimate quality, and makes it possible to balance the influence of each signal on the tracking filter update. The second approach consists in using a different adaptive filter for each signal. A set of constraints links the central frequencies of each filter so that they are as similar as possible. Both methods yield frequency estimates more robust with respect to noise and more stable, without any decrease in estimation accuracy. For the harmonic frequency tracking, we propose a method using the information present in the harmonic component to improve the estimate of the fundamental frequency. The proposed methods also permit to extract the signal components corresponding to the estimated frequencies. These components are very useful for subsequent study. In the second part of this thesis, the algorithms developed in the first part are applied to biomedical signals. Two different applications are studied in this work : electrocardiograms and electroencephalograms. Firstly, a frequency tracking algorithm as well as its multi-signal extension are used to predict the success of electrical cardioversion attempts in patients suffering from atrial fibrillation. The instantaneous frequency is estimated using the algorithms and the corresponding signal component is extracted from electrocardiograms recorded prior to the attempt. With a few parameters computed on the estimated frequency and the corresponding signal component, we were able to predict the result of the cardioversion attempt on our database comprising 18 patients with a success rate of 94% for both algorithms. We think that this result can be very useful for helping the clinician to choose the appropriate therapy for atrial fibrillation management. The developed algorithms are also used to track the oscillatory components present in electroencephalograms. The performance of the basic algorithm is illustrated using single-trial electroencephalogram signals from a visual evoked potential experiment. The algorithm is used to track the gamma component (30-50 Hz). It is able to successfully track the spectral component in spite of the fact that large amplitude variations are present in the signal. A complex version of the multi-signal extension is also used to have an algorithm able to track multiple frequency components on multiple signals. The performance of this algorithm is also illustrated with single-trial electroencephalogram signals. It was shown to be able to correctly track up to four frequency components simultaneously. The quality of the estimation is improved using multiple lead signals.