Graphs.
Nowadays, more and more data natively \live" on the vertices of a graph: brain activity supported by neurons in networks, tra c on transport and energy networks, data from users of social media, complex 3D surfaces describing real objects... Although graphs have been extensively studied in mathematics and computer science, a \signal processing" viewpoint on these objects remains largely to be invented. As such, \signal processing on graphs" (SPG) is an emerging topic, that has already lead to pioneering theoretical and practical work to formalize foundational de nitions and tools. They can be overviewed for instance from [1]. This has opened the path to many exciting future research, calling to revisit most of the usual signal processing tasks ( ltering, denoising, compression, etc.).
Transforms on graphs.
Among signal processing tools, transforms naturally play a key role in modelling data. Thanks to spectral graph theory, a Fourier transform can be de ned on graphs from the eigen decomposition of the graph's Laplacian operator. Various wavelet transforms can also be de ned on graphs, and the teams involved in this proposal have pioneered the design of wavelet transforms on graphs using spectral graph theory. Fourier or wavelet transforms on graphs allow the extension of notions such as the smoothness of a signal. More generally they open the door to using the extensive toolset of sparse signal models that, in recent years, have achieved tremendous success in solving large classes of inverse problems with guaranteed performances and e cient algorithms based on convex optimization [4, 5]. Transposed to general graph data, this leads to applications as diverse as community detection, recommender systems, or matrix completion on graphs [6].
Fast transforms.
The baseline de nition of transforms on graphs does not a priori lead to a fast implementation of the transform, which would counterpart nicely the usual Fast Fourier Transform (FFT) on time-series or images for instance. Designing fast transforms on graphs that mimic the properties of usual fast transforms is desirable for it has the potential to substantially speed up virtually any application of graph transforms, and to scale up these techniques to huge graphs which are needed to address industrial needs for systems on the present and future internet. Spectral graph wavelets developed by LTS2 in collaboration with PANAMA are endowed with fast implementations using Chebyshev polynomials, but more efficient Lanczos methods can be envisioned. However the size and geometry of the underlying graph can substantially impact the computational efficiency of the resulting transform and these effects are still largely unknown. Moreover all current algorithms rely on centralised computations, where the ability to have a distributed implementation is key for big data.
In complement, techniques have recently been developed by the PANAMA team for fast approximate implementations of given transforms, using multi-layer sparse matrix factorization [2]. The classical Fourier transform and its usual FFT implementation easily fall into this framework, as well as the Hadamard transform and other fast transforms, and this opens new perspective to design an (approximate) FFT on graphs.
Objectives.
The postdoc will explore the theory and algorithms of fast transforms on graphs, focusing on applications to big data problems. Leveraging the know-how of the LTS2 and PANAMA team, the postdoc will investigate the potential of message passing and nonconvex optimization techniques to design fast spectral graph wavelets and learned fast transforms. As fundamental tradeo s may exist depending on the underlying graphs structure, the postdoc will conduct a mathematical analysis of the graph characteristics compatible with the existence of fast transforms with certain properties (e.g., spectral and/or spatial localization). Beyond theoretical results, the learned transforms will be benchmarked against existing methods on targeted learning and denoising problems.
Candidate profile.
The ideal candidate should have a degree in electrical engineering, computer science or applied maths. Some experience with any of the topics discussed above is preferable. Ph.D. defense should be posterior to January 1st 2014, with a Ph.D. conducted in a different scientific environment than that envisioned for the postdoc.
Contacts:
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment