A Nearly-Linear Time Framework for Graph-Structured Sparsity
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 4165-4168.
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, our framework achieves an information-theoretically optimal sample complexity for a wide range of parameters. We complement our theoretical analysis with experiments showing that our algorithms also improve on prior work in practice.
@inproceedings{ijcai2016p623,
title = {A Nearly-Linear Time Framework for Graph-Structured Sparsity},
author = {Hegde, Chinmay and Indyk, Piotr and Schmidt, Ludwig},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {4165--4168},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/623},
}
TY - CPAPER TI - A Nearly-Linear Time Framework for Graph-Structured Sparsity AU - Hegde, Chinmay AU - Indyk, Piotr AU - Schmidt, Ludwig T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 4165 EP - 4168 UR - https://ijcai.org/proceedings/2016/623 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
