Coherence (signal processing) | EPFL Graph Search

In signal processing, the coherence is a statistic that can be used to examine the relation between two signals or data sets. It is commonly used to estimate the power transfer between input and output of a linear system. If the signals are ergodic, and the system function is linear, it can be used to estimate the causality between the input and output. Definition and formulation The coherence (sometimes called magnitude-squared coherence) between two signals x(t) and y(t) is a real-valued function that is defined as: ::C_{xy}(f) = \frac{|G_{xy}(f)|^2}{G_{xx}(f) G_{yy}(f)} where Gxy(f) is the Cross-spectral density between x and y, and Gxx(f) and Gyy(f) the auto spectral density of x and y respectively. The magnitude of the spectral density is denoted as |G|. Given the restrictions noted above (ergodicity, linearity) the coherence function estimates the extent to which y(t) may be predicted from x(t) by an optimum linear least squares function. Values of cohe

Graph-based Methods for Visualization and Clustering

Johann Paratte

The amount of data that we produce and consume is larger than it has been at any point in the history of mankind, and it keeps growing exponentially. All this information, gathered in overwhelming volumes, often comes with two problematic characteristics: it is complex and deprived of semantical context. A common step to address those issues is to embed raw data in lower dimensions, by finding a mapping which preserves the similarity between data points from their original space to a new one. Measuring similarity between large sets of high-dimensional objects is, however, problematic for two main reasons: first, high-dimensional points are subject to the curse of dimensionality and second, the number of pairwise distances between points is quadratic with respect to the amount of data points. Both problems can be addressed by using nearest neighbours graphs to understand the structure in data. As a matter of fact, most dimensionality reduction methods use similarity matrices that can be interpreted as graph adjacency matrices. Yet, despite recent progresses, dimensionality reduction is still very challenging when applied to very large datasets. Indeed, although recent methods specifically address the problem of scaleability, processing datasets of millions of elements remain a very lengthy process. In this thesis, we propose new contributions which address the problem of scaleability using the framework of Graph Signal Processing, which extends traditional signal processing to graphs. We do so motivated by the premise that graphs are well suited to represent the structure of the data. In the first part of this thesis, we look at quantitative measures for the evaluation of dimensionality reduction methods. Using tools from graph theory and Graph Signal Processing, we show that specific characteristics related to quality can be assessed by taking measures on the graph, which indirectly validates the hypothesis relating graph to structure. The second contribution is a new method for a fast eigenspace approximation of the graph Laplacian. Using principles of GSP and random matrices, we show that an approximated eigensubpace can be recovered very efficiently, which be used for fast spectral clustering or visualization. Next, we propose a compressive scheme to accelerate any dimensionality reduction technique. The idea is based on compressive sampling and transductive learning on graphs: after computing the embedding for a small subset of data points, we propagate the information everywhere using transductive inference. The key components of this technique are a good sampling strategy to select the subset and the application of transductive learning on graphs. Finally, we address the problem of over-discriminative feature spaces by proposing a hierarchical clustering structure combined with multi-resolution graphs. Using efficient coarsening and refinement procedures on this structure, we show that dimensionality reduction algorithms can be run on intermediate levels and up-sampled to all points leading to a very fast dimensionality reduction method. For all contributions, we provide extensive experiments on both synthetic and natural datasets, including large-scale problems. This allows us to show the pertinence of our models and the validity of our proposed algorithms. Following reproducible principles, we provide everything needed to repeat the examples and the experiments presented in this work.

EPFL2017

Using Anisotropic Diffusion for Coherence Estimation

François Aspert, Jean-Philippe Thiran

In this paper we will present a new coherence estimation technique for SAR interferometry products that adapts the estimation window size and shape during processing. This is of particular interest for sensors with medium spatial resolution, like the ASAR WS mode, where the estimator shall cope with the spatial variability of the targets in the imaged area. This method is designed to remove low coherence magnitude bias while keeping a good spatial resolution. Finally, this new approach will be compared to an existing algorithm for quantifying resulting quality improvement.

2007

Efficient Schemes for Adaptive Frequency Tracking and their Relevance for EEG and ECG

Jérôme Sébastien Van Zaen

Amplitude and frequency are the two primary features of one-dimensional signals, and thus both are widely utilized to analysis data in numerous fields. While amplitude can be examined directly, frequency requires more elaborate approaches, except in the simplest cases. Consequently, a large number of techniques have been proposed over the years to retrieve information about frequency. The most famous method is probably power spectral density estimation. However, this approach is limited to stationary signals since the temporal information is lost. Time-frequency approaches were developed to tackle the problem of frequency estimation in non-stationary data. Although they can estimate the power of a signal in a given time interval and in a given frequency band, these tools have two drawbacks that make them less valuable in certain situations. First, due to their interdependent time and frequency resolutions, improving the accuracy in one domain means decreasing it in the other one. Second, it is difficult to use this kind of approach to estimate the instantaneous frequency of a specific oscillatory component. A solution to these two limitations is provided by adaptive frequency tracking algorithms. Typically, these algorithms use a time-varying filter (a band-pass or notch filter in most cases) to extract an oscillation, and an adaptive mechanism to estimate its instantaneous frequency. The main objective of the first part of the present thesis is to develop such a scheme for adaptive frequency tracking, the single frequency tracker. This algorithm compares favorably with existing methods for frequency tracking in terms of bias, variance and convergence speed. The most distinguishing feature of this adaptive algorithm is that it maximizes the oscillatory behavior at its output. Furthermore, due to its specific time-varying band-pass filter, it does not introduce any distortion in the extracted component. This scheme is also extended to tackle certain situations, namely the presence of several oscillations in a single signal, the related issue of harmonic components, and the availability of more than one signal with the oscillation of interest. The first extension is aimed at tracking several components simultaneously. The basic idea is to use one tracker to estimate the instantaneous frequency of each oscillation. The second extension uses the additional information contained in several signals to achieve better overall performance. Specifically, it computes separately instantaneous frequency estimates for all available signals which are then combined with weights minimizing the estimation variance. The third extension, which is based on an idea similar to the first one and uses the same weighting procedure as the second one, takes into account the harmonic structure of a signal to improve the estimation performance. A non-causal iterative method for offline processing is also developed in order to enhance an initial frequency trajectory by using future information in addition to past information. Like the single frequency tracker, this method aims at maximizing the oscillatory behavior at the output. Any approach can be used to obtain the initial trajectory. In the second part of this dissertation, the schemes for adaptive frequency tracking developed in the first part are applied to electroencephalographic and electrcardiographic data. In a first study, the single frequency tracker is used to analyze interactions between neuronal oscillations in different frequency bands, known as cross-frequency couplings, during a visual evoked potential experiment with illusory contour stimuli. With this adaptive approach ensuring that meaningful phase information is extracted, the differences in coupling strength between stimuli with and without illusory contours are more clearly highlighted than with traditional methods based on predefined filter-banks. In addition, the adaptive scheme leads to the detection of differences in instantaneous frequency. In a second study, two organization measures are derived from the harmonic extension. They are based on the power repartition in the frequency domain for the first one and on the phase relation between harmonic components for the second one. These measures, computed from the surface electrocardiogram, are shown to help predicting the outcome of catheter ablation of persistent atrial fibrillation. The proposed adaptive frequency tracking schemes are also applied to signals recorded in the field of sport sciences in order to illustrate their potential uses. To summarize, the present thesis introduces several algorithms for adaptive frequency tracking. These algorithms are presented in full detail and they are then applied to practical situations. In particular, they are shown to improve the detection of coupling mechanisms in brain activity and to provide relevant organization measures for atrial fibrillation.