تقرير
Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
| العنوان: | Faster Spectral Density Estimation and Sparsification in the Nuclear Norm |
|---|---|
| المؤلفون: | Jin, Yujia, Karmarkar, Ishani, Musco, Christopher, Sidford, Aaron, Singh, Apoorv Vikram |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Computer Science - Machine Learning |
| الوصف: | We consider the problem of estimating the spectral density of the normalized adjacency matrix of an $n$-node undirected graph. We provide a randomized algorithm that, with $O(n\epsilon^{-2})$ queries to a degree and neighbor oracle and in $O(n\epsilon^{-3})$ time, estimates the spectrum up to $\epsilon$ accuracy in the Wasserstein-1 metric. This improves on previous state-of-the-art methods, including an $O(n\epsilon^{-7})$ time algorithm from [Braverman et al., STOC 2022] and, for sufficiently small $\epsilon$, a $2^{O(\epsilon^{-1})}$ time method from [Cohen-Steiner et al., KDD 2018]. To achieve this result, we introduce a new notion of graph sparsification, which we call nuclear sparsification. We provide an $O(n\epsilon^{-2})$-query and $O(n\epsilon^{-2})$-time algorithm for computing $O(n\epsilon^{-2})$-sparse nuclear sparsifiers. We show that this bound is optimal in both its sparsity and query complexity, and we separate our results from the related notion of additive spectral sparsification. Of independent interest, we show that our sparsification method also yields the first deterministic algorithm for spectral density estimation that scales linearly with $n$ (sublinear in the representation size of the graph). Comment: Accepted for presentation at the Conference on Learning Theory (COLT) 2024 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2406.07521 |
| رقم الأكسشن: | edsarx.2406.07521 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |