A Nearly-Linear Time Framework for Graph-Structured Sparsity

We introduce a framework for sparsity structures defined via graphs. Our approach is flexible and generalizes several previously studied spar-sity models. Moreover, we provide efficient pro-jection algorithms for our sparsity model that run in nearly-linear time. In the context of sparse re-covery, we show that our framework achieves an information-theoretically optimal sample com-plexity for a wide range of parameters. We complement our theoretical analysis with experi-ments demonstrating that our algorithms also im-prove on prior work in practice. 1