Sublinear time spectral density estimation

Vladimir Braverman, Aditya Krishnan, Christopher Musco

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    We present a new sublinear time algorithm for approximating the spectral density (eigenvalue distribution) of an n× n normalized graph adjacency or Laplacian matrix. The algorithm recovers the spectrum up to "accuracy in the Wasserstein-1 distance in O(n· (1/")) time given sample access to the graph. This result compliments recent work by David Cohen-Steiner, Weihao Kong, Christian Sohler, and Gregory Valiant (2018), which obtains a solution with runtime independent of n, but exponential in 1/". We conjecture that the trade-off between dimension dependence and accuracy is inherent. Our method is simple and works well experimentally. It is based on a Chebyshev polynomial moment matching method that employees randomized estimators for the matrix trace. We prove that, for any Hermitian A, this moment matching method returns an "approximation to the spectral density using just O(1/") matrix-vector products with A. By leveraging stability properties of the Chebyshev polynomial three-term recurrence, we then prove that the method is amenable to the use of coarse approximate matrix-vector products. Our sublinear time algorithm follows from combining this result with a novel sampling algorithm for approximating matrix-vector products with a normalized graph adjacency matrix. Of independent interest, we show a similar result for the widely used kernel polynomial method (KPM), proving that this practical algorithm nearly matches the theoretical guarantees of our moment matching method. Our analysis uses tools from Jackson's seminal work on approximation with positive polynomial kernels.

    Original languageEnglish (US)
    Title of host publicationSTOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
    EditorsStefano Leonardi, Anupam Gupta
    PublisherAssociation for Computing Machinery
    Number of pages14
    ISBN (Electronic)9781450392648
    StatePublished - Sep 6 2022
    Event54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 - Rome, Italy
    Duration: Jun 20 2022Jun 24 2022

    Publication series

    NameProceedings of the Annual ACM Symposium on Theory of Computing
    ISSN (Print)0737-8017


    Conference54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022


    • approximate matrix-vector multiplication
    • density estimation
    • graph approximation
    • moment matching

    ASJC Scopus subject areas

    • Software


    Dive into the research topics of 'Sublinear time spectral density estimation'. Together they form a unique fingerprint.

    Cite this