Estimation de la densité spectrale et sparsification plus rapide dans la norme nucléaire

Nous considérons le problème de l'estimation de la densité spectrale de la matrice d'adjacence normalisée d'un graphe non orienté à n nœuds. Nous fournissons un algorithme randomisé qui, avec O (n^-2) requêtes à un oracle de degré et de voisinage et en O (n^-3) temps, estime le spectre avec une précision dans la métrique de Wasserstein-1. Cela améliore les méthodes précédentes à la pointe, y compris un algorithme en O (n^-7) de Braverman et al., STOC 2022 et, pour des valeurs suffisamment petites, une méthode en 2^O (^{-1) } de Cohen-Steiner et al., KDD 2018. Pour atteindre ce résultat, nous introduisons une nouvelle notion de sparsification de graphe, que nous appelons sparsification nucléaire. Nous fournissons un algorithme de O (n^-2) requêtes et de O (n^-2) temps pour calculer des sparsificateurs nucléaires O (n^-2) -sparse. Nous montrons que cette limite est optimale à la fois dans sa sparsité et sa complexité de requêtes, et nous séparons nos résultats de la notion connexe de sparsification spectrale additive. D'un intérêt indépendant, nous montrons que notre méthode de sparsification produit également le premier algorithme déterministe pour l'estimation de la densité spectrale qui s'échelonne linéairement avec n (sous-linéaire par rapport à la taille de représentation du graphe).