Information Theoretic Limits for Linear Prediction with Graph-Structured Sparsity

Adarsh Barik, Jean Honorio, Mohit Tawarmalani

We analyze the necessary number of samples for sparse vector recovery in a noisy linear prediction setup. This model includes problems such as linear regression and classification.…