Ementa / bibliografia:
Pré-requisitos: Cálculo Avançado 1; AL Avançada é recomendado, mas não é absolutamente necessário
Ementa:
1) Conjuntos Convexos, Funções Convexas. Cones convexos, Epígrafos, Perspectiva
2) Problemas de otimização. Transformações de problemas e Dualidade de Lagrange. Condições de otimalidade
3) Categorias clássicas: Programação Linear, Programação Quadrática, Programação convexa
4) Categorias cônicas: Cone de Lorentz, Cone Semi-definido
5) Algoritmos: Gradiente, Newton, pontos interiores; análise de convergência e complexidade
Bibliografia:
- Boyd & Vandenberghe, Convex Optimization. Cambridge University Press, 2004
- Andrzej Ruszczyński, Nonlinear Optimization. Princeton University Press, 2006.
- Aaron Ben-Tal e Arkadi Nemirovski, Lectures on Modern Convex Optimization.
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.
1. Descrição
Este é um curso introdutório à teoria dos Espaços Métricos. Trata-se de um curso de nível médio, contemplando a teoria dos espaços métricos em seus aspectos mais fundamentais, cobrindo os principais conceitos e resultados, até as propriedades características do espaços métricos compactos. Tal curso é indicado para estudantes de Economia, Computação, Matemática, Física e outras áreas afins, uma vez que a noção de métrica e distância é fundamental nas áreas acima e em suas áreas de aplicação.
Este curso divide-se em duas partes. Um primeira parte introdutória, na qual são apresentados os conceitos e exemplos básicos de espaços métricos, suas principais propriedades e primeiras aplicações. Na segunda parte inicia-se um estudo mais avançado da teoria dos espaços métricos, na qual tratamos dos espaços métricos completos e dos espaços métricos compactos. Os teoremas de CantorTychonov, Bolzano-Weierstrass e Stone-Weierstrass são estabelecidos, assim como algumas de suas aplicações à Matemática aplicada e à Economia são obtidas.
O Curso apresenta uma duração de 24 Horas, divididas em 12 blocos de 2 Horas. Listas de exercícios, sendo várias destas com sugestões para os problemas mais avançados, servirão de suporte e guia ao efetivo aprendizado.
Seguiremos a seguinte ementa:
2. Ementa do Curso
Capítulo 1 (2 x 2h). Espaços Métricos: motivação, definição, exemplos, isometrias, distância entre conjuntos, bolas e esferas.
Capítulo 2 (2 x 2h). Elementos de Análise: funções contínuas e noções fundamentais da topologia, conjuntos abertos e fechados, métricas equivalentes, transformações lineares.
Capítulo 3 (2 x 2h). Limites e continuidade: sequências, limites de funções, continuidade e continuidade uniforme, aplicações.
Capítulo 4 (3 x 2h). Espaços métricos completos: sequências de Cauchy, espaços de Banach, espaços de Hilbert, completamento de um espaço, extensão de aplicações contínuas, Teorema de Baire, teorema das aproximações sucessivas e aplicações.
Capítulo 5 (3 x 2h). Espaços métricos compactos: espaços compactos, Teorema de Cantor-Tychonov, equicontinuidade, Teoremas de Stone-Weierstrass e aplicações.
3. Pré-requisitos
Recomenda-se um curso básico de Análise real, ao menos um primeiro curso de Cálculo Diferencial, para facilitar a familiarização com os conceitos de limites e funções contínuas. Entretando, é possível acompanhar o curso basicamente partindo da linguagem de conjuntos, que é quase nativa no ser-humano.
4. Bibliografia
[1] Elon Lages Lima: Espaços Métricos. Projeto Euclides, IMPA-CNPq, 1977. (texto principal)
[2] Elon Lages Lima: Curso de Análise, Volume I, Projeto Euclides, IMPA-CNPq, 1976
