Information theoretic limits for linear prediction with graph-structured sparsity

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. We focus on structured graph models. In particular, we prove that sufficient number of samples for the weighted graph model proposed by Hegde and others [2] is also necessary. We use the Fano's inequality [11] on well constructed ensembles as our main tool in establishing information theoretic lower bounds.

• Publication year

  2017

• Venue

  International Symposium on Information Theory

• Publication date

  2017-01-26

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/ISIT.2017.8006949arXiv 1701.07895
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Nearly-Linear Time Framework for Graph-Structured Sparsity

  2015cited by this paper
• A fast approximation algorithm for tree-sparse recovery

  2014cited by this paper
• One-Bit Compressed Sensing: Provable Support and Vector Recovery

  2013cited by this paper
• One-bit compressed sensing with non-Gaussian measurements

  2012cited by this paper
• Sample complexity for 1-bit compressed sensing and sparse classification

  2010cited by this paper
• Information-theoretic bounds on model selection for Gaussian Markov random fields

  2010cited by this paper
• Information-Theoretic Limits of Selecting Binary Graphical Models in High Dimensions

  2009cited by this paper
• Model-Based Compressive Sensing

  2008cited by this paper
• Iterative Hard Thresholding for Compressed Sensing

  2008cited by this paper
• A Simple Proof of the Restricted Isometry Property for Random Matrices

  2008cited by this paper
• Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity

  2008cited by this paper
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples

  2008cited by this paper
• Elements of Information Theory

  2005influential reference
• Assouad, Fano, and Le Cam

  1997cited by this paper
• Festschrift for Lucien Le Cam: Research Papers in Probability and Statistics.

  1997cited by this paper

• Information Theoretic Limits For Standard and One-Bit Compressed Sensing with Graph-Structured Sparsity

  2018influential citation