Euclidean Distance Matrices | EPFL Graph Search

Euclidean distance matrices (EDMs) are central players in many diverse fields including psychometrics, NMR spectroscopy, machine learning and sensor networks. However, they are not often exploited in signal processing. In this thesis, we analyze attributes of EDMs and derive new key properties of them. These analyses allow us to propose algorithms to approximate EDMs and provide analytic bounds on the performance of our methods. We use these techniques to suggest new solutions for several practical problems in signal processing. Together with these properties, algorithms and applications, EDMs can thus be considered as a fundamental toolbox to be used in signal processing. In more detail, we start by introducing the structure and properties of EDMs. In particular, we focus on their rank property; the rank of an EDM is at most the dimension of the set of points generating it plus 2. Using this property, we introduce the use of low rank matrix completion methods for approximating and completing noisy and partially revealed EDMs. We apply this algorithm to the problem of sensor position calibration in ultrasound tomography devices. By adapting the matrix completion framework, in addition to proposing a self calibration process for these devices, we also provide analytic bounds for the calibration error. We then study the problem of sensor localization using distance information by minimizing a non-linear cost function known as the s-stress function in the multidimensional scaling (MDS) community. We derive key properties of this cost function that can be used to reduce the search domain for finding its global minimum. We provide an efficient, low cost and distributed algorithm for minimizing this cost function for incomplete networks and noisy measurements. In randomized experiments, the proposed method converges to the global minimum of the s-stress in more than 99% of the cases. We also address the open problem of existence of non-global minimizers of the s-stress and reduce this problem to a hypothesis. If the hypothesis is true then the cost function has only global minimizers, otherwise, it has non-global minimizers. Using the rank property of EDMs and the proposed minimization algorithm for approximating them, we address an interesting and practical problem in acoustics. We show that using five microphones and one loudspeaker, we can hear the shape of a room. We reformulate this problem as finding the locations of the image sources of the loudspeaker with respect to the walls. We propose an algorithm to find these positions only using first-order echoes. We prove that the reconstruction of the room is almost surely unique. We further introduce a new algorithm for locating a microphone inside a known room using only one loudspeaker. Our experimental evaluations conducted on the EPFL campus and also in the Lausanne cathedral, confirm the robustness and accuracy of the proposed methods. By integrating further properties of EDMs into the matrix completion framework, we propose a new method for calibrating microphone arrays in a diffuse noise field. We use a specific characterization of diffuse noise fields to relate the coherence of recorded signals by two microphones to their mutual distance. As this model is not reliable for large distances between microphones, we use matrix completion coupled with other properties of EDMs to estimate these distances and calibrate the microphone array. Evaluation of our algorithm using real data measurements demonstrates, for the first time, the possibility of accurately calibrating large ad-hoc microphone arrays in a diffuse noise field. The last part of the thesis addresses a central problem in signal processing; the design of discrete-time filters (equivalently window functions) that are compact both in time and frequency. By properly adapting the definitions of compactness in the continuous time to discrete time, we formulate the search for maximally compact sequences as solving a semi-definite program. We show that the spectra of maximally compact sequences are a special class of Mathieu’s cosine functions. Using the asymptotic behavior of these functions, we provide a tight bound for the time-frequency spread of discrete-time sequences. Our analysis shows that the Heisenberg uncertainty bound on the time-frequency spread of sequences is not tight and the lower bound depends on the frequency spread, unlike in the continuous time case.

Sequences with Minimal Time-Frequency Uncertainty

Yann Barbotin, Reza Parhizkar, Martin Vetterli

A central problem in signal processing and communications is to design signals that are compact both in time and frequency. Heisenberg's uncertainty principle states that a given function cannot be arbitrarily compact both in time and frequency, defining an “uncertainty” lower bound. Taking the variance as a measure of localization in time and frequency, Gaussian functions reach this bound for continuous-time signals. For sequences, however, this is not true; it is known that Heisenberg's bound is generally unachievable. For a chosen frequency variance, we formulate the search for “maximally compact sequences” as an exactly and efficiently solved convex optimization problem, thus providing a sharp uncertainty principle for sequences. Interestingly, the optimization formulation also reveals that maximally compact sequences are derived from Mathieu's harmonic cosine function of order zero. We further provide rational asymptotic expansions of this sharp uncertainty bound. We use the derived bounds as a benchmark to compare the compactness of well-known window functions with that of the optimal Mathieu's functions.

Elsevier2015

Sequences with Minimal Time-Frequency Spreads

Yann Barbotin, Reza Parhizkar, Martin Vetterli

For a given time or frequency spread, one can always find continuous- time signals, which achieve the Heisenberg uncertainty principle bound. This is known, however, not to be the case for discrete-time sequences; only widely spread sequences asymptotically achieve this bound. We provide a constructive method for designing sequences that are maximally compact in time for a given frequency spread. By formulating the problem as a semidefinite program, we show that maximally compact sequences do not achieve the classic Heisenberg bound. We further provide analytic lower bounds on the time-frequency spread of such signals.

Ieee2013

Timing is Everything

Karen Adam

In this thesis, timing is everything. In the first part, we mean this literally, as we tackle systems that encode information using timing alone. In the second part, we adopt the standard, metaphoric interpretation of this saying and show the importance of choosing the right time to sample a system, when efficiency is a key consideration.Time encoding machines, or, alternately, integrate-and-fire neurons, encode their inputs using spikes, the timings of which depend on the input and therefore hold information about it. These devices can be made more power efficient than their clocked counterparts and have thus been studied in the fields of signal processing, event-based vision, computational neuroscience and machine learning. However, their timing-based spiking output has so far often been considered a nuisance that one must make do with, rather than a potential advantage. In this thesis, we show that this timing-based output equips spiking devices with capabilities that are out of reach for classical encoding and processing systems.We first discover the benefits of time encoding on multi-channel encoding and recovery of a signal: with time encoding, clock alignment is easy to solve, although it poses problems in the classical sampling scenario. Then, we study the time encoding of low-dimensional signals and see that the asynchrony of spikes allows for a lower sample complexity in comparison with synchronous sampling. Thanks to this same asynchrony, time encoding of video results in an entanglement between spatial sampling density and temporal resolution---a relationship which is not present in frame-based video. Finally, we show that the all-or-none nature of the spikes allows training spiking neural networks in a layer-by-layer fashion---a feat that is impossible with clocked, artificial neural networks, due to the credit assignment problem.The second part of this thesis shows that choosing the right timing of samples can be crucial to ensure efficiency when performing nanoscale magnetic sensing. We are given a stochastic process, where each sample at time t follows a Bernoulli distribution, and which is characterized by oscillation frequencies that we are interested in recovering. We search for an optimal approach to sample this process, such that the variance of the frequencies' estimates is minimized, given constraints on the measurement time. The models we assume stem from the field of nanoscale magnetic sensing, where the number of parameters to be estimated varies with the number of spins one is trying to sense. We present an adaptive approach to choosing samples in both the single-spin and two-spin cases and compare the adaptive algorithm's performance to classical approaches to sampling.In both parts of the thesis, we move away from classical amplitude sampling and consider cases where timing takes the forefront and amplitude information is merely binary, to shows that timing can carry information and that it can control the amount of information gain.

EPFL2022

Timing is Everything

Karen Adam

EPFL2022