Selezione di nodi e pesi per la quadratura su grafi

Sia G(V, E, w) un grafo con V insieme dei vertici di peso iniziale pari a 1 ed E ⊂ V x V insieme di archi rispettivamente di pesi w(xy) > 0. Il nostro obiettivo è quello di trovare un sottoinsieme W ⊂ V di vertici con pesi a(w) tale per cui la somma delle funzioni calcolate in precisi vertici con un proprio peso sia il più simile possibile alla quantità esatta della funzione calcolata su tutti i vertici. Ciò si potrà fare per funzioni f : V → R^n sufficientemente regolari rispetto alla geometria del grafo. I casi migliori dove fare ciò sono quelli in cui f varia regolarmente sul grafo ma in cui è costoso calcolare la funzione in ogni singolo vertice. Studieremo una disuguaglianza mostrando che questo problema si può riscrivere come un problema geometrico e faremo vedere degli esempi in cui si può verificare l’efficacia del metodo, come il problema di heat ball packing o lo studio del database MNIST. Sarà presentato un algoritmo che ci permette di trovare facilmente una buona disposizione dei vertici. Infine tratteremo i design sferici, dei particolari tipi di grafi sulla sfera S^d che ci permettono di approssimare il valore di certi polinomi.