Oberseminar "Mathematik des Maschinellen Lernens und Angewandte Analysis" - MSc. Samuel Mercer

There is significant interest in the study of calculus on graphs, especially regarding the use of gradient-based methods for applications in data driven problems such as classification, clustering and regularisation for inverse problems. Geometric graphs, whose vertices are sampled from a Euclidean domain and whose edge structure is determined by the distance between the nodes in the domain, have been central in theoretical studies. Typical approaches for analysis, such as studying consistency and the existence of continuum limits, rely on Gamma-convergence. This technique has some limitations, as it requires the typical length scale which determines the connectivity structure of the graph to be much larger than the scales frequently used for applications. Moreover, it may fail to provide quantitative results. Within this talk I will discuss necessary and sufficient conditions for a uniform collection of Sobolev inequalities on a sequence of geometric graphs to hold. These inequalities provide quantitative estimates on the Lq regularisation effect of discrete gradients. Furthermore, they hold at a length scale much smaller than that required for the application of Gamma-convergence results.