Curso de Leituras Dirigidas. Mestrado em Matemática Aplicada
Primeiro Semestre 2022/1
Carga horária: 90 horas
Professor: César J. Niche
1. Introdução
Em “Ciência de Dados” frequentemente os dados tem uma estrutura subjacente dada por um grafo G = (V, E) onde os vértices no conjunto E são instâncias desses dados e as arestas em V os vínculos entre eles. Os sinais, i.e. fun¸c˜oes f : V → R definidas no grafo, são frequentemente estudados através de Graph Signal Processing (GSP), ´área para qual as ferramentas clássicas de Digital Signal Processings (DSP) são adaptadas e generalizadas. Tanto GSP quanto DSP tem, na sua base, ferramentas sofisticadas da Análise de Fourier (discreto, contínuo). GSP é uma área de enorme interesse, com desenvolvimento exponencial nos últimos anos, na qual não existe ainda livro-texto de GSP, nem para “engenheiros”, nem para “matemáticos”. Nestas leituras dirigidas trata-se de apresentar ao aluno os elementos (sofisticados, as vezes) da Teoria de Grafos e do Análise de Fourier necessários para ele começar trabalhar numa Dissertação, a partir de 2022/2.
2. Carga horaria e Avaliação
O curso terá uma carga horária de 90 horas. O estudante será avaliado através de um trabalho final escrito de até 10 páginas, extensão e profundação de um tópico visto durante as leituras. Haverá reuniões periódicas (semanais ou quincenais) com o estudante para acompanhar o trabalho deste. Ao longo do semestre serão utilizadas ferramentas computacionais basadas na linguagem Python.
3. Ementa e Bibliografia
3.1 Leituras preliminares. Referencias: Dong, Thanou, Rabat, Frossard [3]; Ortega, Frossard, Kovacevic, Moura and Vanderghynst [7].
Vídeos no Youtube:
Palestra de Antonio Ortega, 2017-2018 ECE Distinguished Lecture Series, University of Delaware.
https://www.youtube.com/watch?v=296S-zh3WnU
Palestra de Xiaowen Dong, London Machine Learning Meetup 2018.
https://www.youtube.com/watch?v=2ds4A11DSOw
3.2 Teoria Espectral de Grafos. Referencias: Chung e Liu [1]; Chung [2]; Gri- goryan [4].
3.3 Análise em Grafos. Referencias: Grigoryan [4]; Pesenson [8], [9].
3.4 Filtros. Referências: Ramakrishna, Wai and Scaglione [11]; Tremblay, Gon¸calves and Borgnat [13].
3.5 Amostragem. Referências: Di Lorenzo, Barbarossa and Banelli [5]; Puy, Tremblay, Gribonval and Vandergheynst [10]; Tanaka, Eldar, Ortega and Cheung [12].
3.6 Aprendizado de Grafos. Referências: Dong, Thanou, Rabat, Frossard [3]; Mateos, Segarra and Marques [6]
Referências
[1] Fan Chung and Linyuan Lu. Complex graphs and networks, volume 107 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2006.
[2] Fan R. K. Chung. Spectral graph theory, volume 92 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997.
[3] Xiaowen Dong, Dorina Thanou, Michael Rabbat, and Pascal Frossard. Learning graphs from data: A signal representation perspective. IEEE Signal Processing Magazine, 36(3):44–63, 2019.
[4] Alexander Grigoryan. Introduction to analysis on graphs, volume 71 of University Lecture Series. American Mathematical Society, Providence, RI, 2018.
[5] PaoloDi Lorenzo, Sergio Barbarossa, and Paolo Banelli. Chapter 9 - sampling and recovery of graph signals. In Petar M. Djuri´c and C´edric Richard, editors, Cooperative and Graph Signal Processing, pages 261–282. Academic Press, 2018.
[6] Gonzalo Mateos, Santiago Segarra, and AntonioG. Marques. Chapter 13 - inference of graph topology. In Petar M. Djuri´c and C´edric Richard, editors, Cooperative and Graph Signal Processing, pages 349–374. Academic Press, 2018.
[7] A. Ortega, P. Frossard, J. Kovaˇcevi´c, J. M. F. Moura, and P. Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808–828, 2018.
[8] Isaac Pesenson. Sampling in Paley-Wiener spaces on combinatorial graphs. Trans. Amer.Math. Soc., 360(10):5603–5627, 2008.
[9] Isaac Z. Pesenson and Meyer Z. Pesenson. Sampling, filtering and sparse approximations on combinatorial graphs. J. Fourier Anal. Appl., 16(6):921–942, 2010.
[10] Gilles Puy, Nicolas Tremblay, R´emi Gribonval, and Pierre Vandergheynst. Random sampling of bandlimited signals on graphs. Appl. Comput. Harmon. Anal., 44(2):446–475, 2018.
[11] Raksha Ramakrishna, Hoi-To Wai, and Anna Scaglione. A user guide to low-pass graph signal processing and its applications: Tools and applications. IEEE Signal Processing Magazine, 37(6):74–85, 2020.
[12] Yuichi Tanaka, Yonina C. Eldar, Antonio Ortega, and Gene Cheung. Sampling signals on graphs: From theory to applications. IEEE Signal Processing Magazine, 37(6):14–30, 2020.
[13] Nicolas Tremblay, Paulo Gon¸calves, and Pierre Borgnat. Chapter 11 - design of graph filters and filterbanks. In Petar M. Djuri´c and C´edric Richard, editors, Cooperative and Graph Signal Processing, pages 299–324. Academic Press, 2018.
