Mathématiques discrètes | EPFL Graph Search

Les mathématiques discrètes, parfois appelées mathématiques finies, sont l'étude des structures mathématiques fondamentalement discrètes, par opposition aux structures continues. Contrairement aux nombres réels, qui ont la propriété de varier "en douceur", les objets étudiés en mathématiques discrètes (tels que les entiers relatifs, les graphes simples et les énoncés en logique) ne varient pas de cette façon, mais ont des valeurs distinctes séparées. Les mathématiques discrètes excluent donc les matières dans les «mathématiques continues» telles que le calcul infinitésimal et l'analyse. Les objets discrets peuvent souvent être énumérés par des entiers. Plus formellement, les mathématiques discrètes ont été caractérisées comme la branche des mathématiques traitant des ensembles dénombrables (ensembles qui ont la même cardinalité que les sous-ensembles des nombres naturels, y compris les nombres rationnels mais pas les nombres réels). Cependant, il n'y a pas de définition exacte du ter

Graph Signal Processing

Ntorina Thanou

Over the past few decades we have been experiencing an explosion of information generated by large networks of sensors and other data sources. Much of this data is intrinsically structured, such as traffic evolution in a transportation network, temperature values in different geographical locations, information diffusion in social networks, functional activities in the brain, or 3D meshes in computer graphics. The representation, analysis, and compression of such data is a challenging task and requires the development of new tools that can identify and properly exploit the data structure. In this thesis, we formulate the processing and analysis of structured data using the emerging framework of graph signal processing. Graphs are generic data representation forms, suitable for modeling the geometric structure of signals that live on topologically complicated domains. The vertices of the graph represent the discrete data domain, and the edge weights capture the pairwise relationships between the vertices. A graph signal is then defined as a function that assigns a real value to each vertex. Graph signal processing is a useful framework for handling efficiently such data as it takes into consideration both the signal and the graph structure. In this work, we develop new methods and study several important problems related to the representation and structure-aware processing of graph signals in both centralized and distributed settings. We focus in particular in the theory of sparse graph signal representation and its applications and we bring some insights towards better understanding the interplay between graphs and signals on graphs. First, we study a novel yet natural application of the graph signal processing framework for the representation of 3D point cloud sequences. We exploit graph-based transform signal representations for addressing the challenging problem of compression of data that is characterized by dynamic 3D positions and color attributes. Next, we depart from graph-based transform signal representations to design new overcomplete representations, or dictionaries, which are adapted to specific classes of graph signals. In particular, we address the problem of sparse representation of graph signals residing on weighted graphs by learning graph structured dictionaries that incorporate the intrinsic geometric structure of the irregular data domain and are adapted to the characteristics of the signals. Then, we move to the efficient processing of graph signals in distributed scenarios, such as sensor or camera networks, which brings important constraints in terms of communication and computation in realistic settings. In particular, we study the effect of quantization in the distributed processing of graph signals that are represented by graph spectral dictionaries and we show that the impact of the quantization depends on the graph geometry and on the structure of the spectral dictionaries. Finally, we focus on a widely used graph process, the problem of distributed average consensus in a sensor network where sensors exchange quantized information with their neighbors. We propose a novel quantization scheme that depends on the graph topology and exploits the increasing correlation between the values exchanged by the sensors throughout the iterations of the consensus algorithm.

EPFL2016

Fourier uniqueness and interpolation in Euclidean space

Martin Peter Stoller

We prove that every Schwartz function in Euclidean space can be completely recovered given only its restrictions and the restrictions of its Fourier transform to all origin-centered spheres whose radii are square roots of integers. In particular, the only Schwartz function which, together with its Fourier transform, vanishes on these spheres, is the zero function. We show that this remains true if we replace the spheres by surfaces or discrete sets of points which are sufficiently small perturbations of these spheres. In a complementary, opposite direction, we construct infinite dimensional spaces of Fourier eigenfunctions vanishing on on certain discrete subsets of those spheres. The proofs combine harmonic analysis, the theory of modular forms and algebraic number theory.

EPFL2022

Le "Fragmentum de inventionibus scientiarum" de Diego Palomino

Nouara Chekhar

The objective of this PhD thesis is the translation of, and the mathematical commentary on, a 16th-century Latin book. Its author, Diego Palomino is not well known. With a background in theology, he was a prior. In order to obtain his PhD at the University of Alcala (Madrid), he submitted a work, De mutations æris, in which he included a collection of what seems to be readings notes, entitled Fragmentum de inventionibus scientiarum. His readings have been drawn from various famous mathematicians of his time and ancient ones. The originality of his work relies mostly on his inventiveness and his style —which can be sarcastic— making the reading of it quite interesting and lively. His work consists for the main part in explaining some unclear demonstrations, or bringing new methods of solution ; he also innovates in solving pairs of indeterminate equations by providing the complete set of integral solutions. Before him, only one mathematician (Abu ̄ K ̄amil, at the end of the 10th century) did so, the other mathematicians restricting themselves to giving only one solution or a pair. Palomino did not hesitate in criticizing a well-established theory in ancient mathematics, namely Archimedes —although his critics seem to rely on a faulty edition. His book is entitled to have a significant place in the history of mathematics, for it both maintains the rigor of Greek classical mathematics and announces innovation, as did the 17th century, culminating with the discovery of the infinitesimal calculus.

EPFL2012

Graph Signal Processing

Ntorina Thanou

EPFL2016