000227982 001__ 227982
000227982 005__ 20190509132610.0
000227982 0247_ $$2doi$$a10.5075/epfl-thesis-7644
000227982 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis7644-7
000227982 02471 $$2nebis$$a10894184
000227982 037__ $$aTHESIS
000227982 041__ $$aeng
000227982 088__ $$a7644
000227982 245__ $$bfundamental limits and applications to machine learning$$aGraph-based structures in data science
000227982 260__ $$bEPFL$$c2017$$aLausanne
000227982 269__ $$a2017
000227982 300__ $$a196
000227982 336__ $$aTheses
000227982 502__ $$aProf. Jean-Philippe Thiran (président) ; Prof. Pierre Vandergheynst (directeur de thèse) ; Prof. Pascal Frossard, Dr Rémi Gribonval, Prof. Antonio Ortega (rapporteurs)
000227982 520__ $$aState-of-the-art data analysis tools have to deal with high-dimensional data. Fortunately, the inherent dimensionality of data is often much smaller, as it has an internal structure limiting its degrees of freedom. In most cases, this structure can be approximated using a graph, i.e, a set of nodes connected by edges. Based on this idea, graphs have been largely used in semi-supervised and unsupervised learning. The canonical assumption when incorporating a graph prior is to assume that the signal is smooth with respect to the graph, i.e, that connected pieces of data have similar values.   Nevertheless, this hypothesis is insufficient to characterize more complex relations between the data and its structure, the graph. To this end, the field of Graph Signal Processing (GSP) extends the graph smoothness hypothesis to a more general assumption. Its key idea is to think of the signal as a sum of harmonic modes, which are obtained from the eigen-decomposition of the Laplacian, an operator representing the second order derivative. Thus, the essence of GSP resides in the Fourier transform defined by the projection on the Laplacian eigenvectors basis, which allows us to filter graph signals.   However, GSP suffers from a counterintuitive irregularity. Contrarily to the classical Fourier basis, the graph Laplacian eigenvectors are not spreading uniformly on the vertex set and can be highly concentrated in a region of the graph. This non-uniformity results in a lack of any intuitive translation operator and consequently poses challenges to generalize some of the classical signal processing theory, e.g., stationarity, uncertainty principles, or sampling. In this thesis, we answer these difficulties by accepting that each node is unique and should be treated specially according to its surrounding structure. This is achieved using an operator called localization that shifts a kernel defined in the spectral domain around a specific node while adapting to the local graph structure.  In the first part of the thesis, we focus on harmonic analysis in GSP. We start by making use of the norm of localized kernels to capture the spectral local features of the graph vertices. To illustrate the relevance of this analysis we then introduce structural clustering, an algorithm that groups nodes according to the role they play in the graph. Then, we bound the vertex-frequency concentration of graph filter banks atoms. Because of the irregular structure of graphs, we construct a local uncertainty principle that is, again, driven by the norm of a localized kernel.   In the second part of the thesis, we tackle GSP problems from a machine learning perspective. We use the localization operator to extend the notion of stationarity to graph signals. It consists of a graph signal probabilistic framework allowing us to optimally solve inverse problems. Finally, we show how the graph total variation can be used in semi-supervised learning and prove its consistency with respect to the underlying graph manifold.
000227982 6531_ $$agraph signal processing
000227982 6531_ $$asemi-supervised learning
000227982 6531_ $$agraph stationarity
000227982 6531_ $$agraph uncertainty principle
000227982 6531_ $$alocal uncertainty principle
000227982 6531_ $$amachine learning
000227982 6531_ $$adata science
000227982 6531_ $$amanifold regularization
000227982 6531_ $$astructural clustering
000227982 6531_ $$aspectral graph theory
000227982 700__ $$0247306$$g179669$$aPerraudin, Nathanaël
000227982 720_2 $$aVandergheynst, Pierre$$edir.$$g120906$$0240428
000227982 8564_ $$uhttps://infoscience.epfl.ch/record/227982/files/EPFL_TH7644.pdf$$zn/a$$s26859314$$yn/a
000227982 909C0 $$xU10380$$0252392$$pLTS2
000227982 909CO $$pthesis$$pthesis-bn2018$$pDOI$$ooai:infoscience.tind.io:227982$$qDOI2$$qGLOBAL_SET$$pSTI
000227982 917Z8 $$x108898
000227982 917Z8 $$x108898
000227982 918__ $$dEDEE$$cIEL$$aSTI
000227982 919__ $$aLTS2
000227982 920__ $$b2017$$a2017-5-11
000227982 970__ $$a7644/THESES
000227982 973__ $$sPUBLISHED$$aEPFL
000227982 980__ $$aTHESIS