Home > Graph-based structures in data science > HTML MARC |

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