Information Theoretic Limits for Linear Prediction with Graph-Structured Sparsity
Adarsh Barik Jean Honorio Mohit Tawarmalani














Information Theoretic Limits for Linear Prediction with Graph-Structured Sparsity
    Adarsh Barik 

Krannert School of Management

Purdue University

West Lafayette, Indiana 47906

Email: abarik@purdue.edu
Jean Honorio 

Department of Computer Science

Purdue University

West Lafayette, Indiana 47906

Email: jhonorio@purdue.edu
Mohit Tawarmalani 

Krannert School of Management

Purdue University

West Lafayette, Indiana 47906

Email: mtawarma@purdue.edu
    
========================================================================================================================================================================================================================================================================================================================================================================================







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 <cit.> is also necessary. We use the Fano's inequality <cit.> on well constructed ensembles as our main tool in establishing information theoretic lower bounds.




  
Keywords:
Compressive sensing, Linear Prediction, Classification, Fano's Inequality, Mutual Information, Kullback Leibler divergence.




§ INTRODUCTION

Sparse vectors are widely used tools in fields related to high dimensional
data analytics such as machine learning, compressed sensing and statistics.
This makes estimation of sparse vectors an important field of research. In a compressive sensing setting, the problem is to closely approximate a d-dimensional signal by an s-sparse vector without losing much information. For regression, this is usually done by observing the inner product of the signal with a design matrix. It is a well known fact that if the design matrix satisfies the Restricted Isometry Property (RIP) then estimation can be done efficiently with a sample complexity of O(s logd/s). Many algorithms such as CoSamp <cit.>, Subspace Pursuit (SP) <cit.> and Iterative Hard Thresholding (IHT) <cit.> provide high probability performance guarantees. Baraniuk and others <cit.> came up with a model based sparse recovery framework. Under this framework, the sufficient number of samples for correct recovery is logarithmic with respect to the cardinality of the sparsity model. 

A major issue with the model based framework is that it does not provide any recovery algorithm on its own. In fact, it is some times very hard to come up with an efficient recovery algorithm. Addressing this issue, Hegde and others <cit.> came up with a weighted graph model for graph structured sparsity and provided a nearly linear time recovery algorithm. They also analyzed the sufficient number of samples for efficient recovery. In this paper, we will provide the necessary condition on the sample
complexity for sparse recovery on a weighted graph model. We will also note that our information theoretic lower bound can be applied not only to linear regression but also to other linear prediction tasks such as classification.

The paper is organized as follows. We describe our setup in Section <ref>. Then we briefly describe the weighted graph model in Section <ref>. We state our results in Section <ref>. In Section <ref>, we apply our technique to some specific examples. At last, we provide some concluding remarks in Section <ref>.



§ LINEAR PREDICTION MODEL


In this section, we introduce the observation model for linear prediction and later specify how to use it for specific problems such as linear regression and classification. 
Formally, the problem is to estimate an s-sparse vector β̅ from noisy observations of the form, 

    z = f(X β̅ + e) ,

where z ∈ℝ^n is the observed output, X ∈ℝ^n × d is the design matrix , e ∈ℝ^n is a noise vector and f:ℝ^n→ℝ^n is a fixed function. Our task is to recover β̅∈ℝ^d from the observations z.





 §.§ Linear Regression
 

Linear regression is a special case of the above by choosing f (x) = x. Then we simply have,

    z = X β̅ + e  .

Prior work analyzes the sample complexity of sparse recovery for the linear regression setup. In particular, if the design matrix X satisfies the Restricted Isometry Property (RIP) then algorithms such as CoSamp <cit.>, Subspace Pursuit (SP) <cit.> and Iterative Hard Thresholding (IHT) <cit.> can recover β̅ quite efficiently and in a stable way with a sample complexity of O(s logd/s). Furthermore, it is known that Gaussian random matrices (or sub-Gaussian in general) satisfy RIP <cit.>. If we choose our design matrix to be a Gaussian matrix and we have a good sparsity model that incorporates extra information on the sparsity structure then we can reduce the sample complexity to O(log m_s) where m_s is number of possible supports in the sparsity model, i.e., the cardinality of the sparsity model <cit.>. In the same line of work, Hegde and others <cit.> proposed a weighted graph based sparsity model to efficiently learn β̅.  





 §.§ Classification

We can model binary classification problems by choosing f(x) = (x) or in other words, we can have,

    z = (X β̅ + e)  .

Similar to the linear regression setup, there is also prior work <cit.>, <cit.>, <cit.>, on analyzing the sample complexity of sparse recovery for binary classification problem (also known as 1-bit compressed sensing). 

Since arguments for establishing information theoretic lower bounds are not algorithm specific, we can extend our basic argument to the both settings mentioned above. For comparison, we will use the results by Hegde and others <cit.> in a linear regression setup. 



§ WEIGHTED GRAPH MODEL (WGM)


In this section, we introduce the Weighted Graph Model (WGM) and formally state the sample complexity results from <cit.>. The Weighted Graph Model is defined on an underlying graph G = (V,E) whose vertices are on the coefficients of the unknown s-sparse vector β̅∈ℝ^d i.e. V = [d] = {1, 2, …, d}. Moreover, the graph is weighted and thus we introduce a weight function w : E →ℕ. Borrowing some notations from <cit.>,  for a forest F ⊆ G we denote ∑_e ∈ F w_e as w(F). B denotes the weight budget, s denotes the sparsity (number of non-zero coefficients) of β̅ and g denotes the number of connected components in F. The weight-degree ρ(v) of a node v ∈ V is the largest number of adjacent nodes connected by edges with the same weight, i.e.,

    ρ(v) = max_b ∈ N |{ (v', v) ∈ E |  w(v',v) = b }|  .
  
We define the weight-degree of G, ρ(G) to be the maximum weight-degree of any v ∈ V. Next, we define the Weighted Graph Model on coefficients of β̅ as follows:    


	
	The (G, s, g, B)-WGM is the set of supports defined as
	
    𝕄 = { S ⊆ [d]  |  |S| = s  and  ∃ F ⊆ G with V_F = S, . 
    . γ(F) = g, w(F) ≤ B } ,

 
where γ(F) is number of connected components in a forest F. Authors in  <cit.> provide the following sample complexity result for linear regression under their model:

	Let β̅∈ℝ^d be in the (G, s, g, B)-WGM. Then 
	
    n = O(s(logρ(G) + logB/s) + g logd/g)

	i.i.d. Gaussian observations suffice to estimate β̅. More precisely, let e ∈ℝ^n be an arbitrary noise vector from equation (<ref>) and X be an i.i.d. Gaussian matrix. Then we can efficiently find an estimate β̂ such that 
	
    β̅ - β̂≤ C e ,

	where C is a constant indepenedent of all variables above.



Notice that in the noiseless case (e = 0), we recover the exact β̅. We will prove that information-theoretically, the bound on the sample complexity is tight and thus the algorithm of <cit.> is statistically optimal. 
 



§ MAIN RESULTS


In this section, we will state our results for both the noiseless and the noisy case. We establish an information theoretic lower bound on linear prediction problem defined on WGM. We use Fano's inequality <cit.> to prove our result by carefully constructing an ensemble, i.e., a WGM. Any algorithm which infers β̅ from this particular WGM would require a minimum number of samples. Note that the use of restricted ensembles is customary for information-theoretic lower bounds <cit.> <cit.>. It follows that in the case of linear regression, the  upper bound on the sample complexity by Hegde and others <cit.> is indeed tight. 





 §.§ Noiseless Case

 Here, we provide a necessary condition on the sample complexity for exact recovery in the noiseless case. More formally, 

	
	There exists a particular (G, s, g, B)-WGM, and a particular set of weights for the entries in the support of β̅ such that if we draw a β̅∈ℝ^d uniformly at random and we have a data set 𝒮 of n ∈ o((s-g) (logρ(G) + logB/s-g) + g logd/g + (s - g) logg/s - g + s log 2) i.i.d. observations as defined in equation (<ref>) with e = 0 then P(β̅≠β̂) ≥1/2 irrespective of the procedure we use to infer β̂ on (G,s,g,B)-WGM from 𝒮.  
 

	We use Fano's inequality <cit.> on a carefully chosen restricted ensemble to prove our theorem. A detailed proof can be found in appendix.






 §.§ Noisy Case

A similar result can be stated for the noisy case. However, in this case recovery is not exact but is sufficiently close in l_2-norm with respect to noise in the signal. Another thing to note is that in <cit.> inferred β̂ can come from a slightly bigger WGM model but here we actually infer β̂ from the same WGM. 

	
	There exists a particular (G, s, g, B)-WGM, and a particular set of weights for the entries in the support of β̅ such that if we draw a β̅∈ℝ^d uniformly at random and we have a data set 𝒮 of n ∈ o((s-g) (logρ(G) + logB/s-g) + g logd/g + (s-g) logg/s-g + s log 2) i.i.d. observations as defined in equation (<ref>) with e_i iid∼𝒩(0,σ), ∀ i ∈{1 … n } then  ℙ(β̅ - β̂≥ C  e ) ≥1/10 for 0 < C ≤ C_0 irrespective of the procedure we use to infer β̂ on (G,s,g,B)-WGM from 𝒮.


	Note that when s ≫ g and B ≥ s-g then Ω((s-g) (logρ(G) + logB/s-g) + g logd/g + (s - g) logg/s - g +  slog 2) is roughly Ω(s(logρ(G) + logB/s) + g logd/g).


	We will prove this result in three steps. First, we will carefully construct an underlying graph G for the WGM. Second, we will
	bound mutual information between β̅ and 𝒮 by bounding the Kullback-Leibler (KL) divergence. Third, we will bound the size of properly defined restricted ensemble to complete our proof.
	
	
	

  
Constructing an underlying graph G for the WGM We construct an underlying graph for the WGM using the following steps:
	
		
  * Divide d nodes equally into g groups with each group having d/g nodes.
		
  * For each group j, we denote a node by N_i^j where j is the group index and i is the node index. Each group j, contains nodes from N_1^j to N_d/g^j.
		
  * We allow for circular indexing, i.e., a node N_i^j where i > d/g is same as node N_i - d/g^j.  
		
  * For each p = 1,…,B/s-g, node N_i^j has an edge with nodes N_i+(p -1)ρ(G)/2 + 1^j to N_i+p ρ(G)/2^j with weight p.
		
  * Cross edges between nodes in two different groups are allowed as long as they have edge weights greater than B/s-g and they do not affect ρ(G). 
	
	Figure <ref> shows an example of a graph constructed using the above steps. Furthermore, parameters for our WGM satisfy the following requirements:
	
		
  R1. d/g≥ρ(G)B/s-g + 1,
		
  R2. ρ(G)B/2(s-g)≥s/g - 1,
		
  R3. B ≥ s-g .
	 
	These are quite mild requirements (see appendix) on the parameters and are easy to fulfill. Figure <ref> shows one graph which follows our construction and also fulfills R1, R2 and R3. 
	We define our restricted ensemble ℱ on G as:
	
    ℱ   = {β | β_i = 0,  if  i ∉ S, β_i ∈{C_0σ√(d)/√(2(1 - ϵ)), .. 
       . . C_0σ√(d)/√(2(1 - ϵ)) + C_0σ√(d)/√((1 - ϵ))},   if  i ∈ S, S ∈𝕄} ,

	for some 0 < ϵ < 1 and 𝕄 is as in Definition <ref>.
	
	Our true β̅ is picked uniformly at random from the above restricted ensemble. We will prove that on this restricted ensemble, our Theorem <ref> holds. We will make use of following lemmas for our proof:
	
		
		Given the restricted ensemble ℱ,
		
    β̅ - β̂≤C_0σ√(d)/√((1-ϵ))β̅ = β̂ .

		
	We are dealing with high dimensional cases, hence	moving forward we will assume that n < d. We state another lemma:
	
		
		For some 0 < ϵ < 1,
		
    ℙ(e ^2 ≤σ^2 n/1 - ϵ) ≥ 1 - exp(-ϵ^2 n/4) .

	
	From Lemma <ref>, Lemma <ref> and using the fact that 
	d > n and C ≤ C_0, the corollary below follows:
	
		
		
    ℙ(β̅ - β̂≥ C  e  |  β̅≠β̂) ≥ 1 - exp(-ϵ^2 n/4) .

	
	

  
Bound on the mutual information  We will assume that the elements of design matrix X have been chosen at random and independently from 𝒩(0, 1). The linear prediction problem  from Section <ref> can be described by the following Markov's chain:
	
    β̅→ y = X β̅ + e → z = f (y ) →β̂ .
 
	Lets say 𝒮 contains n i.i.d. observations of z and 𝒮' contains n i.i.d. observations of y. Then using the data processing inequality <cit.> we can say that,
	
    𝕀(β̅, 𝒮) ≤𝕀(β̅, 𝒮') .

	Hence, for our purpose it suffices to have an upper bound on 𝕀(β̅, 𝒮'). Now we can bound the mutual information by the following <cit.>:
	
    𝕀(β̅, 𝒮') ≤1/|ℱ|^2∑_β∈ℱ^∑_β' ∈ℱ^𝕂𝕃(ℙ_𝒮'|βℙ_𝒮'|β' ) ,

	where 𝕂𝕃 is the Kullback-Leibler divergence. Note that 𝒮' consists of n i.i.d. observations of y. Hence,
	
    𝕀(β̅, 𝒮') ≤n/|ℱ|^2∑_β∈ℱ^∑_β' ∈ℱ^𝕂𝕃(ℙ_y_i|βℙ_y_i|β' )

	Furthermore, from equation (<ref>) and noting that the elements of X come independently from 𝒩(0, 1),
	
    y_i =  X_i β + e_i
       y_i|β∼𝒩(0 , β^2 + σ^2 )  
       y_i|β' ∼𝒩(0 , β' ^2 + σ^2 ) .

	We can bound the Kullback-Leibler divergence between ℙ_y_i|β and ℙ_y_i|β' as follows:
	
    𝕂𝕃(ℙ_y_i|βℙ_y_i|β')    = 1/2(β^2 + σ^2/β' ^2 + σ^2 - 1 . 
       . - logβ^2 + σ^2/β' ^2 + σ^2) 
       ≤1/2(β^2 + σ^2/β' ^2 + σ^2 - 1 - 1 + β' ^2 + σ^2/β^2 + σ^2) 
       ≤1/2((C_0σ√(d)/√(2(1-ϵ)) + C_0σ√(d)/√((1-ϵ)))^2 s  + σ^2/(C_0σ√(d)/√(2(1-ϵ)))^2 s + σ^2. 
       . + (C_0σ√(d)/√(2(1-ϵ)) + C_0σ√(d)/√((1-ϵ)) )^2 s + σ^2/(C_0σ√(d)/√(2(1-ϵ)) )^2 s + σ^2 - 2 ) 
       ≤1/2(2 (C_0σ√(d)/√(2(1-ϵ)) + C_0σ√(d)/√(1-ϵ))^2 s  + σ^2/(C_0σ√(d)/√(2(1-ϵ)))^2 s + σ^2 - 2 ) 
       ≤1/2(2 (√(2)+1)^2(C_0σ√(d)/√(2(1-ϵ)))^2 s  + σ^2/(C_0σ√(d)/√(2(1-ϵ)))^2 s + σ^2 - 2 ) 
       ≤ (√(2)+1)^2 - 1 
       ≤ 5  .

	The first inequality holds because 1 - 1/x≤log x, ∀ x > 0, the second inequality holds by taking the largest value of numerators and the smallest value of denominators. The other inequalities follow from simple algebraic manipulation. Substituting 𝕂𝕃(ℙ_y_i|βℙ_y_i|β') in equation (<ref>) we get,
	
    𝕀(β̅, 𝒮') ≤  5 n  .
 



  
Bound on |ℱ| Now we will count elements in ℱ to complete our proof. We present the following counting argument to establish a lower bound on all the possible supports for our restricted ensemble:

	
  * We choose one node from each of the g groups in underlying graph G to be root of a connected component. Each group has d/g possible candidates for the root and hence we can choose them in (d/g)^g possible ways.
	
  * Since we are interested only in establishing a lower bound on ℱ, we will only consider the cases where each connected component has s/g nodes. Moreover, given a root node N_i^j in group j, we will choose the remaining s/g - 1 nodes connected with the root only from the nodes N_i+1^j to nodes N_i+Bρ(G)/2(s - g)^j (using circular indices if needed). Construction of the graph G allows us to do this. At least till the last ρ(G)B/2(s - g) nodes, we always include node N_i^j and we never include N_r^j, r ≤ i-1 in our selection. Furthermore, R1 guarantees that we have enough nodes to avoid any possible repetitions due to circular indices for the last ρ(G)B/2(s -g) nodes and R2 ensures that we have enough nodes to form a connected component. This guarantees that all the supports are unique. Hence, given a root node N_i^j we have ρ(G)B/2(s-g)s/g -1 choices which across all the groups comes out to be (ρ(G)B/2(s - g)s/g -1 )^g.     
	
  * Each entry in the support of β can take two values which can either be C_0σ√(d)/√(2(1 - ϵ)) or C_0σ√(d)/√(2(1 - ϵ)) + C_0σ√(d)/√((1 - ϵ)). 

It should be noted that any support chosen using the above steps satisfies constraint on weight budget, i.e., w(F) ≤ B as the maximum edge weight in any connected component will always be less than or equal to B/s-g. Combining all the above steps together we get:

    |ℱ|    ≥ 2^s (d/g)^g (ρ(G)B/2(s - g)s/g -1 )^g 
       ≥ 2^s (d/g)^g (ρ(G)Bg/2(s-g)^2)^(s-g) .


Using Fano's inequality <cit.> and results from equation (<ref>) and equation (<ref>), it is easy to prove the following lemma,

	
	If n ∈ o(log |ℱ|) then ℙ(β̂≠β̅) ≥1/2. 


By using Bayes' Theorem and combining Corollary <ref> and Lemma <ref>,

    ℙ(β̅ - β̂≥ Ce)    ≥ℙ(β̅ - β̂≥ Ce, β̅≠β̂) 
       = ℙ(β̅ - β̂≥ Ce |  β̅≠β̂) 
       ℙ(β̅≠β̂)
       ≥(1 - exp(-ϵ^2 n/4)) 1/2 .

The last inequality (<ref>) holds when n is o(log |ℱ|). We also know that n ≥ 1 and if we choose ϵ≥√(-4log 0.8)∼ 0.9448, then we can write inequality (<ref>) as,

    ℙ(β̅ - β̂≥ Ce)    ≥1/10 .





§ SPECIFIC EXAMPLES


Here, we will provide counting arguments for some of the well-known sparsity structures, such as tree sparsity and block sparsity models. It should be noted that barring the count of possible supports in the specific model our technique can be used to prove lower bounds of the sample complexity for other sparsity structures. 



 §.§ Tree-structured sparsity model


The tree-sparsity model <cit.>, <cit.> is used in many applications such as wavelet decomposition of piecewise smooth signals and images. In this model, we assume that the coefficients of the s-sparse signal form a k-ary tree and the support of the sparse signal form a rooted and connected sub-tree on s nodes in this k-ary tree. The arrangement is such that if a node is part of this subtree then its parent is also included in it. Here, we will discuss the case of a binary tree which can be generalized to a k-ary tree. In particular, the following proposition provides a lower bound on the number of possible supports of an s-sparse signal following a binary tree-structured sparsity model.


In a binary tree-structured sparsity model ℱ, log |ℱ| ≥ cs for some c > 0. 
   
The proof of the proposition <ref> follows from the fact that we have at least 2^s different choices of β̅ in our restricted ensemble.   
From the above and following the same proof technique as before, it is easy to prove the following corollary for the noisy case (a similar result holds for the noiseless case as well).


In a binary tree-structured sparsity model, if n ∈ o(s) then ℙ(β̅ - β̂≥ C  e ) ≥1/10.

Essentially, Corollary <ref> proves that the O(s) sample complexity achieved in <cit.> is optimal for the tree-sparsity model.



 §.§ Block sparsity model


In the block sparsity model, <cit.>, an s-sparse signal, β∈ℝ^J × N, can be represented as a matrix with J rows and N columns. The support of β comes from K columns of this matrix such that s = J K. More precisely, 

	
    𝒮_K = {β = [ β_1 …β_N ]∈ℝ^J × N such that . 
    . β_n = 0 for n ∉ L, L ⊆{1,…, N}, |L|=K } .

 

The above can be modeled as a graph model. In particular, we can construct a graph G over all the elements in β by treating nodes in the column of the matrix as connected nodes (see Fig. <ref>) and then our problem is to choose K connected components from N.    




It is easy to see that the number of possible supports in this model, ℱ, would be, |ℱ| = 2^KJN  K≥ 2^KJ (N/K)^K. Correspondingly the necessary number of samples for efficient signal recovery comes out to be Ω(KJ + K logN/K). An upper bound of O(KJ + K logN/K) was derived in <cit.> which matches our lower bound. 




§ CONCLUDING REMARKS


We proved that the necessary number of samples required to efficiently recover a sparse vector in the weighted graph model is of the same order as the sufficient number of samples provided by Hegde and others <cit.>. Moreover, our results not only pertain to linear regression but also apply to linear prediction problems in general.

1
	
baraniuk2010model
R. G. Baraniuk, V. Cevher, M. F. Duarte, and C. Hegde, “Model-based
compressive sensing,” IEEE Transactions on Information Theory,
vol. 56, no. 4, pp. 1982–2001, 2010.


hegde2015nearly
C. Hegde, P. Indyk, and L. Schmidt, “A nearly-linear time framework for
graph-structured sparsity,” in Proceedings of the 32nd International
	Conference on Machine Learning (ICML-15), pp. 928–937, 2015.

blumensath2009iterative
Thomas Blumensath and Mike E Davies.
Iterative hard thresholding for compressed sensing.
Applied and Computational Harmonic Analysis, 27(3):265–274,
2009.

dai2008subspace
Wei Dai and Olgica Milenkovic.
Subspace pursuit for compressive sensing: Closing the gap between
performance and complexity.
Technical report, DTIC Document, 2008.

needell2009cosamp
Deanna Needell and Joel A Tropp.
Cosamp: Iterative signal recovery from incomplete and inaccurate
samples.
Applied and Computational Harmonic Analysis, 26(3):301–321,
2009.

baraniuk2008simple
Richard Baraniuk, Mark Davenport, Ronald DeVore, and Michael Wakin.
A simple proof of the restricted isometry property for random
matrices.
Constructive Approximation, 28(3):253–263, 2008.


hegde2014fast
Chinmay Hegde, Piotr Indyk, and Ludwig Schmidt.
A fast approximation algorithm for tree-sparse recovery.
In 2014 IEEE International Symposium on Information Theory,
pages 1842–1846. IEEE, 2014.

Yu97
B. Yu.
Assouad, Fano, and Le
Cam.
In Torgersen E. Pollard D. and Yang G., editors, Festschrift for
	Lucien Le Cam: Research Papers in Probability and Statistics, pages
423–435. Springer New York, 1997.

gupta2010sample
Ankit Gupta, Robert D Nowak, and Benjamin Recht.
Sample complexity for 1-bit compressed sensing and sparse
classification.
In ISIT, pages 1553–1557, 2010.

gopi2013one
Sivakant Gopi, Praneeth Netrapalli, Prateek Jain, and Aditya V Nori.
One-bit compressed sensing: Provable support and vector recovery.
In ICML (3), pages 154–162, 2013.

Cover06
T. Cover and J. Thomas.
Elements of Information Theory.
John Wiley & Sons, 2nd edition, 2006.

ai2014one
Albert Ai, Alex Lapanowski, Yaniv Plan, and Roman Vershynin.
One-bit compressed sensing with non-gaussian measurements.
Linear Algebra and its Applications, 441:222–239, 2014.

santhanam2012information
Narayana P Santhanam and Martin J Wainwright.
Information-theoretic limits of selecting binary graphical models in
high dimensions.
IEEE Transactions on Information Theory, 58(7):4117–4134,
2012.

wang2010information
Wei Wang, Martin J Wainwright, and Kannan Ramchandran.
Information-theoretic bounds on model selection for gaussian markov
random fields.
In Information Theory Proceedings (ISIT), 2010 IEEE
	International Symposium on, pages 1373–1377. IEEE, 2010.







§ APPENDIX



§ PROOF OF LEMMA <REF>


	First note that when β̅ = β̂ then its obvious that Lemma <ref> holds. Here, we will prove that two arbitrarily chosen β_1 and β_2 such that β_1, β_2 ∈ℱ where β_1 ≠β_2 then β_1 - β_2 ≥C_0σ√(d)/√(1-ϵ). ℱ is as defined in equation (<ref>).
	

  
β_1 and β_2 have the same support Since we assume that β_1 ≠β_2, thus they must differ in at least one position on their support. Lets say that one such position is i. Then,   
	
    β_1 - β_2   ≥ |β_1i - β_2i| 
       =C_0σ√(d)/√(1 - ϵ) .

	

  
β_1 and β_2 have different supports When β_1 and β_2 have different supports then we can always find i and j such that i ∈ S_1, i ∉ S_2 and j ∉ S_1, j ∈ S_2 where S_1 and S_2 are supports of β_1 and β_2 respectively. Then, 
	
    β_1 - β_2    ≥√(β_1i^2 + β_2j^2 )
       ≥√((C_0σ√(d)/√(2(1 - ϵ)) )^2+ (C_0σ√(d)/√(2(1 - ϵ)))^2 )
       =C_0σ√(d)/√(1 - ϵ) .

	Since this is true for any two arbitrarily chosen β_1 and β_2, hence it holds for β̅ and β̂ as well. This proves the lemma.




§ PROOF OF LEMMA <REF>


	
    ℙ(  e ^2 ≥σ^2 n/1-ϵ)    = ℙ(exp(λ/2e/σ^2) ≥exp(λ/2n/1-ϵ))
       ≤𝔼[exp(λ/2e/σ^2)]/exp(λ/2n/1-ϵ)
       =exp(-λ/2n/1 -ϵ) (1/1-λ)^n/2 .
 
	The first equality holds for any λ > 0, we take 0 < λ < 1 . The second inequality comes from Markov's inequality. The last equality follows since e_i/σiid∼𝒩(0, 1). Now, by taking λ = ϵ,
	
    ℙ( e ^2 ≥σ^2 n/1-ϵ)    ≤exp(-n/2(ϵ/1 -ϵ + log (1-ϵ)))
       ≤exp(-ϵ^2 n/4)  .

	The last inequality holds because for 0 < ϵ < 1, ϵ/1 -ϵ + log (1-ϵ) ≥ϵ^2/2. This proves our lemma,
	
    ℙ( e ^2 ≤σ^2 n/1-ϵ)    ≥ 1 - exp(-ϵ^2 n/4)  .

 




§ PROOF OF LEMMA <REF>


	Using Fano's inequality <cit.>, we can say that,
	
    ℙ(β̂≠β̅)    ≥ 1 - 𝕀(β̅, 𝒮) + log 2/log |ℱ|
       ≥ 1 - 𝕀(β̅, 𝒮') + log 2/log |ℱ|
       ≥ 1 - 5n + log 2/log |ℱ| .

	The first inequality follows from equation (<ref>) and the second inequality follows from the upper bound on the mutual information established in equation (<ref>). Now, we want ℙ(β̂≠β̅) ≤1/2, then it follows that n must be,
	
    n ≥1/10log |ℱ| - 1/5log 2  .

	This proves the lemma.
	




§ PROOF OF THEOREM <REF>



  * 

  
Constructing an underlying graph G We assume that our underlying graph G fulfills all the properties mentioned while proving Theorem <ref>. On this underlying graph G, we define our restricted ensemble ℱ as:

    ℱ   = {β_i ∈{ 1, -1}, if i ∈ S, else β_i = 0, S ∈𝕄} ,
 
where 𝕄 is as in Definition <ref>.



  
Bound on the mutual information We will assume that the elements of design matrix X have been chosen at random and independently from 𝒩(1/s √(2), 1/s). As in the proof of Theorem <ref>, we can describe noiseless linear prediction problem as the following Markov's chain:

    β̅→ y = X β̅→ z = f (y ) →β̂ .
 
Lets say 𝒮 contains n i.i.d. observations of z and 𝒮' contains n i.i.d. observations of y. Then using the data processing inequality <cit.>, we can say that,

    𝕀(β̅, 𝒮) ≤𝕀(β̅, 𝒮')  .

Hence, for our purpose it suffices to have an upper bound on 𝕀(β̅, 𝒮'). Now using results from <cit.>, 

    𝕀(β̅, 𝒮') ≤1/|ℱ|^2∑_β∈ℱ^∑_β' ∈ℱ^𝕂𝕃(ℙ_𝒮'|βℙ_𝒮'|β' )  .

where 𝕂𝕃 is the Kullback-Leibler divergence. Note that 𝒮' consists of n i.i.d. observations of y. Hence,

    𝕀(β̅, 𝒮') ≤n/|ℱ|^2∑_β∈ℱ^∑_β' ∈ℱ^𝕂𝕃(ℙ_y_i|βℙ_y_i|β' )  .

Furthermore from equation (<ref>) and noting that the elements of X come independently from 𝒩(1/s√(2), 1/s),

    y_i =  X_i β
        y_i|β∼𝒩(∑_k=1^dβ_k/s √(2) , 1)  
        y_i|β' ∼𝒩(∑_k=1^dβ'_k/s√(2), 1)  .

We can bound 𝕂𝕃(ℙ_y_i|βℙ_y_i|β') by,

    𝕂𝕃(ℙ_y_i|βℙ_y_i|β')    = 1/2( ∑_k=1^d (β_k - β'_k) /s√(2)  )^2 
       ≤ 1  .

Substituting 𝕂𝕃(ℙ_y_i|βℙ_y_i|β') in equation (<ref>) we get,

    𝕀(β̅, 𝒮') ≤  n  .




  
Bound on |ℱ| Using a similar counting logic used in Theorem <ref>, we can get:

    |ℱ|    ≥ 2^s (d/g)^g (ρ(G)Bg/2(s-g)^2)^(s-g) .
 
We prove the theorem by substituting the mutual information from equation (<ref>) and |ℱ| from equation (<ref>) in the Fano's inequality <cit.>.






§ DISCUSSION ON THE REQUIREMENTS FOR THE UNDERLYING GRAPH G

We mentioned before that R1, R2 and R3 are quite mild requirements on the parameters. In fact, it is easy to see that,


Given any value of s, g and B ≥ s - g, there are infinitely many choices for ρ(G) and d that satisfy R1 and R2 and hence, there are infinitely many (G, s, g, B)-WGM which follow our construction. 


	R3 is readily satisfied if each edge has at least unit edge weight and we are not forced to choose isolated nodes in support. Most of the graph-structured sparsity models fulfill this requirement. R2 gives us a lower bound on the choice of ρ(G),
	
    ρ(G) ≥2(s-g)^2/Bg .

	Similarly, given a value of ρ(G), R1 just provides a lower bound on choice of d,
	 
    d ≥g ρ(G)B/s-g + g  .

	 Clearly, there is an infinite number of combinations for ρ(G) and d.  

 


