A Nearly-Linear Time Framework for Graph-Structured Sparsity
Chinmay Hegde, Piotr Indyk, Ludwig Schmidt · 2015
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.
Cited by 58 works.
Authors
References
- Reducibility among Combinatorial Problems
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Decoding by Linear Programming
- Model Selection and Estimation in Regression with Grouped Variables
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- A General Approximation Technique for Constrained Forest Problems
- Reducibility Among Combinatorial Problems
- Structured Compressed Sensing: From Theory to Applications
- Group lasso with overlap and graph lasso
- A Sparse-Group Lasso