A nearly-linear time framework for graph-structured sparsity

Chinmay Hegde, Piotr Indyk, Ludwig Schmidt

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

    Abstract

    We introduce a framework for sparsity structures defined via graphs. Our approach is flexible and generalizes several previously studied sparsity models. Moreover, we provide efficient projection algorithms for our sparsity model that run in nearly-linear time. In the context of sparse recovery, we show that our framework achieves an information-theoretically optimal sample complexity for a wide range of parameters. We complement our theoretical analysis with experiments demonstrating that our algorithms also improve on prior work in practice.

    Original languageEnglish (US)
    Title of host publication32nd International Conference on Machine Learning, ICML 2015
    EditorsDavid Blei, Francis Bach
    PublisherInternational Machine Learning Society (IMLS)
    Pages928-937
    Number of pages10
    ISBN (Electronic)9781510810587
    StatePublished - 2015
    Event32nd International Conference on Machine Learning, ICML 2015 - Lile, France
    Duration: Jul 6 2015Jul 11 2015

    Publication series

    Name32nd International Conference on Machine Learning, ICML 2015
    Volume2

    Other

    Other32nd International Conference on Machine Learning, ICML 2015
    CountryFrance
    CityLile
    Period7/6/157/11/15

    ASJC Scopus subject areas

    • Human-Computer Interaction
    • Computer Science Applications

    Fingerprint Dive into the research topics of 'A nearly-linear time framework for graph-structured sparsity'. Together they form a unique fingerprint.

    Cite this