Fourier could be a data scientist: From graph Fourier transform to signal processing on graphs

Benjamin Ricaud, Nicolas Tremblay, Pierre Vandergheynst
ELSEVIER FRANCE-EDITIONS SCIENTIFIQUES MEDICALES ELSEVIER, 2019
Journal paper

Abstract

The legacy of Joseph Fourier in science is vast, especially thanks to the essential tool that the Fourier transform is. The flexibility of this analysis, its computational efficiency and the physical interpretation it offers makes it a cornerstone in many scientific domains. With the explosion of digital data, both in quantity and diversity, the generalization of the tools based on Fourier transform is mandatory. In data science, new problems arose for the processing of irregular data such as social networks, biological networks or other data on networks. Graph signal processing is a promising approach to deal with those. The present text is an overview of the state of the art in graph signal processing, focusing on how to define a Fourier transform for data on graphs, how to interpret it and how to use it to process such data. It closes showing some examples of use. Along the way, the review reveals how Fourier's work remains modern and universal, and how his concepts, coming from physics and blended with mathematics, computer science, and signal processing, play a key role in answering the modern challenges in data science. (C) 2019 Academie des sciences. Published by Elsevier Masson SAS.

Official source

https://infoscience.epfl.ch/record/271408?ln=en

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

Related publications (10)

Networks are data structures that are fundamental for capturing and analyzing complex interactions between objects. While they have been used for decades to solve problems in virtually all scientific fields, their usage for data analysis in real-world practical applications deserves to be further investigated. In this thesis, we explore multiple aspects of network science and show how the design of new graph-based approaches offers an unprecedented depth for analyzing complex datasets. Through the study of practical applications, we demonstrate how to extract key findings in several domains such as digital humanities, recommender systems, social behavior, neuroscience or knowledge discovery. First, we propose to define in a concise manner the data science workflow. We present the tools, techniques, and questions that the practitioner needs to have in mind when addressing a new large-scale problem as they are of tremendous importance if one wants to apply network science concepts to real applications. Based on this foundation chapter, we begin by demonstrating the worth of networks for music recommendation with Genezik, our smart playlist application that adapts to user taste. Using signal processing, machine learning, and graphs, we show how to improve the performance of recommender systems as well as proposing a radically different user experience that has yet to be found in competing systems. We then move on to the introduction of the causal multilayer graph of activity, a novel graph method dedicated to the analysis of dynamical processes over networks. More than a data structure, we present a data analysis approach that tracks spreading or propagation of events through time in a scalable manner by efficiently combining a network with values associated with its vertices. Used in four different applications, the analysis of spatio-temporal patterns of activity extracted from the causal multilayer graph helps us better understand how rumors spread in social networks or how brain regions interact in resting states for instance. Finally, we study the browsing behavior of millions of people on Wikipedia and show how to extract contextual patterns of activity that reflect what is collectively remembered from past events. Based on their analysis, we confirm social studies on human behavior and conclude by revealing some of the rules that define human curiosity.

EPFL2017

Text as signal. A tutorial with case studies focusing on social media (Twitter)

Erick Jorge Canales Rodriguez

Sentiment analysis is the automated coding of emotions expressed in text. Sentiment analysis and other types of analyses focusing on the automatic coding of textual documents are increasingly popular in psychology and computer science. However, the potential of treating automatically coded text collected with regular sampling intervals as a signal is currently overlooked. We use the phrase "text as signal" to refer to the application of signal processing techniques to coded textual documents sampled with regularity. In order to illustrate the potential of treating text as signal, we introduce the reader to a variety of such techniques in a tutorial with two case studies in the realm of social media analysis. First, we apply finite response impulse filtering to emotion-coded tweets posted during the US Election Week of 2020 and discuss the visualization of the resulting variation in the filtered signal. We use changepoint detection to highlight the important changes in the emotional signals. Then we examine data interpolation, analysis of periodicity via the fast Fourier transform (FFT), and FFT filtering to personal value-coded tweets from November 2019 to October 2020 and link the variation in the filtered signal to some of the epoch-defining events occurring during this period. Finally, we use block bootstrapping to estimate the variability/uncertainty in the resulting filtered signals. After working through the tutorial, the readers will understand the basics of signal processing to analyze regularly sampled coded text.

SPRINGER2022

Wavelet footprints and frames for signal processing and communication

Pier Luigi Dragotti

Linear transforms and expansions are fundamental mathematical tools of signal processing. In particular, the wavelet transform has played an important role in several signal processing tasks, compression being a prime example. A signal can be represented in a basis or a frame. Frames, which are an extension of bases to overcomplete sets of vectors, are sometimes preferred to bases because of their greater design freedom and recently they have had an important impact in signal processing. This thesis focuses on the design of new bases and frames for signal processing and communications. The first contribution of the thesis is the exploration of the use of oversampled filter banks, which represent a possible way to implement frames, to robust communications. Normally, transforms are used as a pure source coding method and a reliable communication is obtained with a channel coder which follows the source coder. In this case, we use frames to achieve efficient source compression and robustness to transmission errors at the same time. In the context of pure source transform coding, we investigate the performance of the wavelet transform and study the dependency of the wavelet coefficients across scales. This analysis leads to the design of a new expansion which provides an efficient representation of piecewise smooth signals. We call footprints the elements of this expansion. The main property of footprints is that they efficiently characterize the singular structures of the signal, which usually carry the main information. We show that algorithms based on footprints outperform wavelet methods in different applications such as denoising, compression and deconvolution. Finally, we study a particular source coding technique called multiple description coding. This technique is used for data transmission over unreliable networks. In multiple description coding, the coder generates several different descriptions of the same signal and the decoder can produce a useful reconstruction of the source with any received subset of these descriptions. We study the problem of multiple description coding of stationary Gaussian sources with memory. First, we compute the multiple description rate distortion region for these sources. Then, we develop an algorithm for the design of optimal critically sampled filter banks for multiple description coding of Gaussian sources.

EPFL2002

EPFL2017

Wavelet footprints and frames for signal processing and communication

Pier Luigi Dragotti

EPFL2002