{'fraction_non_alphanumeric': 0.03317210802095929, 'fraction_numerical': 0.00826279725916969, 'mean_word_length': 4.102416452442159, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On sensing capacity of sensor networks for the class of linear observation, fixed SNR models

In this paper we address the problem of finding the sensing capacity of sensor networks for a class of linear observation models and a fixed SNR regime. Sensing capacity is defined as the maximum number of signal dimensions reliably identified per sensor observation. In this context sparsity of the phenomena is a key feature that determines sensing capacity. Precluding the SNR of the environment the effect of sparsity on the number of measurements required for accurate reconstruction of a sparse phenomena has been widely dealt with under compressed sensing. Nevertheless the development there was motivated from an algorithmic perspective. In this paper our aim is to derive these bounds in an information theoretic set-up and thus provide algorithm independent conditions for reliable reconstruction of sparse signals. In this direction we first generalize the Fano's inequality and provide lower bounds to the probability of error in reconstruction subject to an arbitrary distortion criteria. Using these lower bounds to the probability of error, we derive upper bounds to sensing capacity and show that for fixed SNR regime sensing capacity goes down to zero as sparsity goes down to zero. This means that disproportionately more sensors are required to monitor very sparse events. Our next main contribution is that we show the effect of sensing diversity on sensing capacity, an effect that has not been considered before. Sensing diversity is related to the effective \emph{coverage} of a sensor with respect to the field. In this direction we show the following results (a) Sensing capacity goes down as sensing diversity per sensor goes down; (b) Random sampling (coverage) of the field by sensors is better than contiguous location sampling (coverage).

sparsity on the number of measurements required for accurate reconstruction of a sparse phenomena has been widely dealt with under compressed sensing. Nevertheless the development there was motivated from an algorithmic perspective. In this paper our aim is to derive these bounds in an information theoretic set-up and thus provide algorithm independent conditions for reliable reconstruction of sparse signals.
In this direction we first generalize the Fano's inequality and provide lower bounds to the probability of error in reconstruction subject to an arbitrary distortion criteria. Using these lower bounds to the probability of error, we derive upper bounds to sensing capacity and show that for fixed SNR regime sensing capacity goes down to zero as sparsity goes down to zero. This means that disproportionately more sensors are required to monitor very sparse events. We derive lower bounds to sensing capacity (achievable) via deriving upper bounds to the probability of error via adaptation to a max-likelihood detection set-up under a given distortion criteria. These lower bounds to sensing capacity exhibit similar behavior though there is an SNR gap in the upper and lower bounds. Subsequently, we show the effect of correlation in sensing across sensors and across sensing modalities on sensing capacity for various degrees and models of correlation. Our next main contribution is that we show the effect of sensing diversity on sensing capacity, an effect that has not been considered before. Sensing diversity is related to the effective coverage of a sensor with respect to the field. In this direction we show the following results (a) Sensing capacity goes down as sensing diversity per sensor goes down; (b) Random sampling (coverage) of the field by sensors is better than contiguous location sampling (coverage). In essence the bounds and the results presented in this paper serve as guidelines for designing efficient sensor network architectures.

I. INTRODUCTION
In this paper we study fundamental limits to the performance of sensor networks for a class of linear sensing models under a fixed SNR regime. Fixed SNR is an important and necessary ingredient for sensor network applications where the observations are inevitably corrupted by external noise and clutter. In addition we are motivated by sensor network applications where the underlying phenomena exhibits sparsity. Sparsity is manifested in many applications for which sensor networks are deployed, e.g. localization of few targets in a large region, search for targets from among a large number of sites e.g. land mine detection, estimation of temperature variation for which few spline coefficients may suffice to represent the field , i.e. phenomena is sparse under a suitable transformation. More recent applications such as that considered in [1] also involve imaging a sparse scattering medium.
The motivation for considering linear sensing models comes from the fact that in most cases the observation at a sensor is a superposition of signals that emanate from different sources, locations etc.
For e.g., in seismic and underground borehole sonic applications, each sensor receives signals that is a superposition of signals arriving from various point/extended sources located at different places. In radar applications [1], [2], under a far field assumption the observation system is linear and can be expressed as a matrix of steering vectors. In this case the directions becomes the variable space and one looks for strategies to optimally search using many such radars. Statistical modulation of gain factors in different directions is feasible in these scenarios and is usually done to control the statistics of backscattered data.
In other scenarios the scattering medium itself induces random gain factors in different directions.
In relation to signal sparsity compressive sampling, [3], [4] has shown to be very promising in terms of acquiring minimal information, which is expressed as minimal number of random projections, that suffices for adequate reconstruction of sparse signals. Thus in this case too, the observation model is linear. In [5] this set-up was used in a sensor network application for realizing efficient sensing and information distribution system by combining with ideas from linear network coding. Also it was used in [6] to build a wireless sensor network architecture using a distributed source-channel matched communication scheme.
For applications related to wireless sensor networks where power limited sensors are deployed, it becomes necessary to compress the data at each sensor. For e.g. consider a parking surveillance system where a network of wireless low resolution cameras are deployed, [7]. With each camera taking several snapshots in space and transmitting all of them to a base station will overwhelm the wireless link to the base station. Instead transmission overhead is significantly reduced by sending a weighted sum of the observations. An illustration is shown in figure 1. A similar set-up was also considered in [8] for a robotic exploration scenario.
Motivated by the scenarios considered above we start with sensing (observation) models where at a sensor the information about the signal is acquired as a projection of the signal onto a weight vector.
Under this class of observation model, the sensing model is linear and is essentially a matrix, G ∈ R m×n chosen from some appropriate class particular to the application. In this work we consider a fixed SN R model (see also [9]) where the observations at m sensors for the signal X ∈ X n are given by, where each row of the matrix G is restricted to have a unit ℓ 2 norm and where N is the noise vector with unit noise power in each dimension. It is important to consider fixed SNR scenario particularly for applications related to sensor networks. Practically each sensor is power limited. In an active sensing scenario the sensors distribute this power to sense different modalities, or to look (beamform) in various directions. Thus we restrict the ℓ 2 norm of each row of G to be unity and then scale the system model February 1, 2008 DRAFT appropriately by SN R. For a networked setting we assume that the observations made at the sensors are available for processing at a centralized location or node. In case when this is infeasible or costly, information can be exchanged or aggregated at each sensor using distributed consensus type algorithms, such as that studied in [10].
In order utilize the information theoretic ideas and tools, we adopt a Bayesian perspective and assume a prior distribution on X. Another motivation for considering a Bayesian set-up is that one can potentially model classification/detection scenarios where prior information is usually available and is useful. Note that under some technical conditions it can be shown that a lower bound to the Bayesian error is also lower bound to worst case probability of error for the parametric set-up. Therefore the lower bounds presented in this paper also provide lower bounds to the parameter estimation problem.
In this paper we capture the system performance via evaluating asymptotic upper and lower bounds to the ratio C(d 0 ) = n m such that reconstruction to within a distortion level d 0 is feasible. We call the ratio C(d 0 ) as sensing capacity : the number of signal dimensions reliably identified per projection (sensor). This term was coined in [11] in the context of sensor networks for discrete applications.
Alternatively, bounds to C(d 0 ) can be interpreted as providing scaling laws for the minimal number of sensors/projections required for reliable monitoring/signal reconstruction.
For a signal sparsity level of k, a different ratio of k m also seems to be a reasonable choice, but in most cases k is unknown and needs to be determined, e.g., target density, or sparsest signal reconstruction.
Here it is important to penalize false alarms, misclassification costs. Furthermore, n and m are known and part of the problem specification, while signal complexity is governed by k, and one of our goals is to understand performance as a function of signal complexity. In this paper we show that sensing capacity C(d 0 ) is also a function of signal sparsity apart from SN R.
The upper bounds to C(d 0 ) are derived via finding lower bounds to the probability of error in reconstruction subject to a distortion criteria, that apply to any algorithm used for reconstruction. The achievable (lower) bounds to C(d 0 ) are derived via upper bounding the probability of error in a max-likelihood detection set-up over the set of rate distortion quantization points. Since most of the development for these classes of problems has been algorithmic, [3], [9], our motivation for the above development is driven by the need to find fundamental algorithm independent bounds for these classes of problems. In particular, under an i.i.d model on the components of X that models a priori information, e.g. sparsity of X, and lettingX(Y) denote the reconstruction of X from Y, then we show that, for some appropriate distortion measure d(., .) and where R X (d 0 ) is the corresponding scalar rate distortion function; K(n, d 0 ) is bounded by a constant and it depends on the number of neighbors of a quantization point in an optimal n−dimensional rate distortion mapping.
Next, we consider the effect of structure of G on the performance. Using the result on the lower bound on the probability of error given by equation (2), a necessary condition is immediately identified in order that the reconstruction to within an average distortion level d 0 is feasible, which is, . For a fixed prior on X the performance is then determined by the mutual information term that in turn depends on G. This motivates us to consider the effect of the structure of G on the performance and via evaluation of I(X; Y|G) for various ensembles of G we quantify the performance of many different scenarios that restrict the choice of G for sensing. Under the case when G is chosen independently of X and randomly from an ensemble of matrices (to be specified later in the problem set-up), we have This way of expanding allow us to isolate the effect of structure of the sensing matrix G on the performance which in principle influences bounds on C(d 0 ) through the change in mutual information as captured via the equations 3-5 and as applied to satisfy the necessary conditions prescribed by the lower bound in equation (2).
Using the above idea, in this paper we will show the effect of sensing diversity on the performance, a concept which is explained next. Under the sensing model as prescribed above, at each sensor one can relate each component of the corresponding projection vector as contributing towards diversity in sensing. The total number of non-zero components in the projection vector is called sensing diversity.
This terminology is analogous to that used in MIMO systems in the context of communications. As will be shown later on that loss in sensing capacity is not very significant at reasonable levels of sensing diversity (with randomization in sampling per sensor). In fact there is a saturation effect that comes into play, which implies that most of the gains can be obtained at diversity factor close to 0.5. Now if one considers the noiseless case, i.e. Y = GX, then it was shown in [3] that for some m and for some sparsity k as a function of n and the coherence of the sensing matrix, an ℓ 1 optimization problem : To this end note that if G is sparse then solving the above system is computationally faster as is shown in [12].
There are other types of modalities that arise in the context of resource constrained sensor networks.
As an example consider the application in [7] where each camera may be physically restricted to sample contiguous locations in space or under limited memory it is restricted to sample few locations, possibly at random. This motivates us to consider other structures on G under such modalities of operation. In this paper we will contrast random sampling and contiguous sampling and show that random sampling is better than contiguous sampling. In such scenarios it becomes important to address a coverage question and in some cases may lead to a poor performance. In highly resource constrained scenarios randomization in elements of G is not feasible. In this direction we also consider an ensemble of {0, 1} matrices, with and without randomization in the locations of non-zero entries in each row. To facilitate the reading of the paper we itemize the organization as follows.
1. We present the problem set-up in section II where we make precise the signal models and the ensembles of sensing matrices that will be considered in relation to different sensor networking scenarios.
2. In section III we will present the lower bounds to the probability of error in reconstruction subject to an average distortion criteria. The development is fairly general and is self-contained.
3. In section IV we will present a constructive upper bound to the probability of error in reconstruction subject to an average ℓ 2 distortion criteria. The development there is particular to the fixed SNR linear sensing model that is the subject of the present paper, though the ideas are in general applicable to other sensing models and to other classes of distortion measures.
4. Once we establish the upper and lower bounds, we will use the results to obtain upper and lower bounds to sensing capacity for the fixed SNR linear sensing models, in sections V and VI. In these sections we will consider the full diversity Gaussian ensemble for sensing matrix. The motivation to consider this model is that the mutual information and moment generating functions are easier to evaluate for the Gaussian ensemble. This is thus useful to gain initial insights into the tradeoffs of signal sparsity and SNR.
February 1, 2008 DRAFT 5. Since the bounds to sensing capacity can be interpreted as providing bounds for number of projections/sensors for reliable monitoring, in section VII we will compare the scaling implied by bounds to sensing capacity to that obtained in [9] in the context of complexity penalized regularization framework.
6. In section VIII we consider the effect of the structure of the sensing matrix G on sensing capacity.
The section is divided into several subsections. We begin by considering the effect of sensing diversity on sensing capacity. Following that we consider the effect of correlation in the columns of G on achievable sensing capacity. Then we consider a very general case of a deterministic sensing matrix and via upper bounding the mutual information we comment on the performance of various types of sensing architectures of interest.
7. In section IX we consider the {0, 1} ensemble for sensing matrices and provide upper bounds to sensing capacity for various modalities in sensing. 8. In section X we give an example of how our methods can be extended to handle cases when one is interested in reconstruction of functions of X rather than X itself. In this direction we will consider the case of recovery of sign patterns of X.

II. PROBLEM SET-UP
Assume that the underlying signal X lies in an n-dimensional space X n , where X can be discrete or continuous. Discrete X models scenarios of detection or classification and continuous X models scenarios of estimation.
a) Fixed SNR model: : The observation model for the sensors is a linear observation model and is given by, which is the fixed SN R model as described in the introduction. The matrix G ∈ R m×n is a random matrix selected from an ensemble which we will state subsequently. For all m, n each row of G is restricted to have a unit ℓ 2 norm. The noise vector N is i.i.d. Gaussian unit variance in each dimension.

A. Discussion about fixed SNR model
At this point it is important to bring out an important distinction of the assumption and subsequently analysis of a fixed SNR model in contrast to similar scenarios considered but in albeit high SNR setting.
The observation model of equation 1 studied in this paper is related to a class of problems that have been central in statistics. In particular it is related to the problem of regression for model order selection.
In this context the subsets of columns of the sensing matrix G form a model for signal representation which needs to be estimated from the given set of observations. The nature selects this subset in a weighted/non-weighted way as modeled by X. The task is then to estimate this model order and thus X. In other words estimate of X in most cases is also linked to the estimate of the model order under some mild assumptions on G. Several representative papers in this direction are [13], [14], [15] that consider the performance of several (signal) complexity penalized estimators in both parametric and nonparametric framework. One of the key differences to note here is that the analysis of these algorithms is done for the case when SN R → ∞, i.e. in the limit of high SNR which is reflected by taking the additive noise variance to go to zero or not considering the noise at all. However SNR is an important and necessary ingredient for applications related to sensor networks and therefore we will not pursue a high SNR development here. Nevertheless the results obtained are directly applicable to such scenarios.
In the next section we will first outline prior distribution(s) on X, that reflect the sparsity of the signal X and the model for realizing sensing diversity in the sensing matrix G. Then we will outline the choices of ensembles for the sensing matrix G. In the following N (m, σ 2 ) denotes the Gaussian distribution with mean m and variance σ 2 .
B. Generative models of signal sparsity and sensing diversity b) Signal sparsity: In a Bayesian set-up we model the sparsity of the phenomena by assuming a mixture distribution on the signals X. In particular the n dimensional vector X = X 1 , ..., X n is a sequence drawn i.i.d from a mixture distribution where α ≤ 1 2 . In this paper we consider two cases.
1) Discrete Case: m 1 = 1 and m 0 = 0 and σ 1 = σ 0 = 0. This means that X is a Bernoulli(α) sequence. This models the discrete case for addressing problems of target localization, search, etc.
In this context we call α the sparsity ratio which is held fixed for all values of n. Under the above model, on an average the signal will be k sparse where k = αn. Note that k → ∞ as n → ∞.
February 1, 2008 DRAFT c) Sensing diversity and ensemble for G: In connection to the model for diversity, the sensing matrix G is random matrix such that for each row i, G ij , j = 1, 2, .., n are distributed i.i.d according to . We consider three cases: The matrix is then normalized so that each row has a unit ℓ 2 norm. In this context we call β as the (sensing) diversity ratio. Under the above model, on an average each sensor will have a diversity of l = βn. Note that l → ∞ as n → ∞. Given the set-up as described above the problem is to find upper and lower bounds to ) for some distortion measure d(., .) defined on X × X . In this paper we will consider Hamming distortion measure for discrete X and squared distortion measure for the continuous X. Under this set-up we exhibit the following main results: 1) Sensing capacity C(d 0 ) is also a function of SN R, signal sparsity and sensing diversity.
2) For a fixed SNR sensing capacity goes to zero as sparsity goes to zero.
3) Low diversity implies low sensing capacity. 4) Correlations across the columns and across the rows of G leads to decrease in sensing capacity. 5) For the {0, 1} ensemble for sensing matrices, sensing capacity for random sampling is higher than for contiguous sampling.
In the next section we will provide asymptotic lower bounds on the probability of error in reconstruction subject to a distortion criteria. Following that we will provide a constructive upper bound to the probability of error. We will then use these results to evaluate upper and lower bounds to sensing capacity. In the following we will use X and X n interchangeably.

III. BOUNDS TO THE PERFORMANCE OF ESTIMATION ALGORITHMS: LOWER BOUNDS
Lemma 3.1: Given observation(s) Y for the sequence X n {X 1 , ..., X n } of random variables drawn i.i.d. according to P X . LetX n (Y) be the reconstruction of X n from Y. Also is given a distortion where K(d 0 , n) is bounded by a constant and where R X (d 0 ) is the corresponding (scalar) rate distortion function for X.
Proof: See Appendix.
Essentially, K(n, d 0 ) = 1 n × log(♯ neighbors of a quantization point in an optimal n-dimensional ratedistortion mapping). NOTE: The assumption of a scalar valued process in lemma 3.1 is taken for the sake of simplicity. The results are easily generalizable and can be extended to the case of vector valued processes.
For the simpler case of discrete parameter space, the lower bound to the minimax error in a parameter estimation framework is related to the Bayesian error as follows, where Θ is the parameter space and P Θ is the class of probability measures over Θ and π ∈ P is any particular distribution. The above result holds true for the case of continuous parameter space under some mild technical conditions. Thus a lower bound to the probability of error as derived in this paper also puts a lower bound on the probability of error for the parametric set-up. In our set-up we will choose π as a probability distribution that appropriately models the a priori information on X, e.g. signal sparsity.
For modeling simple priors such as sparsity on X one can choose distributions that asymptotically put most of the mass uniformly over the relevant subset of Θ and is a key ingredient in realization of the lower bound on probability of error derived in this paper.
We have the following corollary that follows from lemma 3.1.
., X n be an i.i.d. sequence where each X i is drawn according to some distribution P X (x) and X n ∈ X n , where |X | is finite. Given observation Y about X n we have,

A. Tighter bounds for discrete X under hamming distortion
The results in the previous section can be stated for any finite n without resorting to the use of AEP for the case of discrete alphabets, with hamming distortion as the distortion measure and for certain values of the average distortion constraint d 0 . We have the following lemma.

Lemma 3.2:
Given observation(s) Y for the sequence X n {X 1 , ..., X n } of random variables drawn i.i.d. according to P X . Then for hamming under distortion measure d H (., .), for X i ∈ X , |X | < ∞ and for distortion levels,

B. Comment on the proof technique
The proof of lemma 3.1 closely follows the proof of Fano's inequality [16], where we start with a distortion error event based on 1 n d(X(Y), X) ≥ d 0 and then evaluate conditional entropy of a ratedistortion mapping conditioned on the error event and the observation Y. To bound K(n, d 0 ), we use results in [17] for the case of squared distortion measure.
In relation to the lower bounds presented in this paper for the probability of reconstruction subject to an average distortion level one such development was considered in [18] in the context of a non-parametric regression type problem. Let θ be an element of the metric space (d, Θ). Then given {Y i , G i } m i=1 for some random or non-random vectors G i ∈ R n and Y i being the responses to these vectors under θ.
Also is given the set of conditional pdfs given by p θ(Gi) (Y i ) where the notation means that that the pdfs are parametrized by θ(G i ). The task is to find a lower bound on the minimax reconstruction distortion under measure d, in reconstruction of θ given Y and G. In our case one can identify X θ and Θ X n with squared metric d. For such a set-up lower bounds on the asymptotic minimax expected distortion in reconstruction (not the probability of such an event) was derived in [18] using a variation of Fano's bound (see [19]) under a suitable choice of worst case quantization for the parameter space Our derivation has a flavor of this method in terms of identifying the right quantization, namely the rate distortion quantization for a given level of average distortion in a Bayesian setting. Although we evaluate the lower bounds to the probability of error and not the expected distortion itself, the lower bound on the expected distortion in reconstruction follows immediately. Moreover our method works for any distortion metric d, though in this paper we will restrict ourselves to cases of interest particular to sensor networks applications.

IV. CONSTRUCTIVE UPPER BOUND TO THE PROBABILITY OF ERROR
In this section we will provide a constructive upper bound to the probability of error in reconstruction subject to an average squared distortion level. Unlike the lower bounds in this section we will provide upper bounds for the particular observation model of equation (6). This could potentially be generalized but we will keep our focus on the problem at hand.
To this end, given ǫ > 0 and n, assume that we are given the functional mapping f (X n ) (or f (X)) that corresponds to the minimal cover at average distortion level d 0 as given by lemma 11.2. Upon receiving the observation Y the aim is to map it to the index corresponding index f (X), i.e. we want to detect which distortion ball the true signal belongs to. Clearly if X is not typical there is an error. From lemma 11.1, the probability of this event can be bounded by an arbitrary δ > 0 for a large enough n. So we will not worry about this a-typical event in the following.
Since all the sequences in the typical set are equiprobable, we covert the problem to a max-likelihood detection set-up over the set of rate-distortion quantization points given by the minimal cover as follows.
Given G we and the rate distortion points corresponding to the functional mapping f (X n ), we enumerate the set of points, GZ n i ∈ R m . Then given the observation Y we map Y to the nearest point (in R m ) GZ n i . Then we ask the following probability, that is, we are asking what is the probability that the in typical max-likelihood detection set-up we will map signals from distortion ball B i to signals in distortion ball B j that is at an average set distance For sake of brevity we denote the above probability via P e (pair) to reflect it as a pairwise error probability. Since the noise is additive Gaussian Since noise N is AWGN noise with unit variance in each dimension, its projection onto the unit vector ||G(X−X ′ )|| is also Gaussian with unit variance. Thus we have By a standard approximation to the Q(.) (error) function, we have that, In the worst case we have the following bound, Now note that from above construction it implies that the average distortion in reconstruction of X is bounded by 2d 0 if the distortion metric obeys triangle inequality. To evaluate the total probability of error we use the union bound to get, We will use this general form and apply it to particular cases of ensembles of the sensing matrix G.
In the following sections we begin by providing upper and lower bounds to the sensing capacity for the Gaussian ensemble for full diversity.

A. Discrete X, full diversity, Gaussian ensemble
For this case we have the following main lemma.
Since G is random we take expectation over G. It can be shown that the mutual information E G I(X n ; Y|G) ≤ max PX: Proof: From lemma 5.1 we have that E G I(X; Y|G) ≤ m 2 log(1 + αSN R). In order that the probability of error be lower bounded by zero, from lemma 3.1 it follows that asymptotically It can be shown that |K(d 0 , n) − log 2| < ǫ with ǫ very small for large enough n, see e.g. [17]. The lemma then follows by plugging in the results from section XI-C.
It can be easily seen that as α ↓ 0 the sensing capacity goes to zero. We illustrate this by plotting the upper bounds in figure 2 for the discrete case. We will revisit this phenomena in section VII in relation to the bounds derived in [5] in the context of compressed sensing.

A. Discrete alphabet, full diversity
The discrete X with hamming distortion is a special case where we can provide tighter upper bounds.
The proof follows from the development in section IV and identifying that for the discrete case one can choose the discrete set of points instead of the distortion balls. We have the following lemma. Lemma 6.1: Given X ∈ X n with |X | < ∞, for β = 1 and G chosen from a Gaussian ensemble.
Then for d 0 ≤ min x∈X P X (x), a sensing capacity of is achievable in that the probability of error goes down to zero exponentially for choices of C = n m = C(d 0 ) − η for any η > 0.

Proof: We have
where we have applied the union bound to all the typical sequences that are outside the hamming distortion ball of radius d 0 . Taking the expectation with respect to G we get, Now note that since G is a Gaussian random matrix where each row has a unit ℓ 2 norm, ||G(X − is a sum of m independent χ 2 random variables with mean ||X − X ′ || 2 . Thus from the moment generating function of the χ 2 random variable we get that, Now note that for d 0 ≤ α, log n nd0 ≥ nd 0 log 1 d0 . Then from above one can see that the probability of error goes down to zero if, Thus a sensing capacity of is achievable in that the probability of error goes down to zero exponentially for choices of C = n m = C(d 0 ) − η for any η > 0.

B. Continuous X, full diversity
is achievable in that the probability of error goes down to zero exponentially with n for C = n m ≤ C(2d 0 ) − ǫ for some arbitrary ǫ > 0.
Proof: For this case we invoke the construction as outlined in section IV. From the results in that section we get that, Note that the result is little weaker in that guarantees are only provided to reconstruction within d 0 , but one can appropriately modify the rate distortion codebook to get the desired average distortion level. Proceeding as in the case of discrete X and , by taking the expectation over G and noting that min X∈Bi,X ′ ∈Bj ||X − X ′ || 2 ≥ 2nd 0 , we get that, This implies that for the probability of error goes to zero exponentially. This means that a sensing capacity of is achievable in that the probability of error goes down to zero exponentially with n for C = n m ≤ C(d 0 ) − η for some arbitrary η > 0.

VII. COMPARISON WITH EXISTING BOUNDS
Note that the results in this paper are stated for d 0 ≤ α for the discrete case and for d 0 ≤ α 2 for the continuous case. This is because one must consider stricter average distortion measures as the phenomena becomes sparser. To bring out this point concretely and for purposes of comparison with existing bounds, we consider the result obtained in [5] based on optimal complexity regularized estimation framework.
They show that the expected mean squared error in reconstruction is upper bounded by, where C 1 ∼ 1 and C 2 ∼ 50(P + σ) 2 {(1 + p) log 2 + 4}, under normalization of the signal and the noise power and p is the number of quantization levels, [9]. To this end consider an extremely sparse case, i.e., k = 1. Then the average distortion metric in equation 9, does not adequately capture the performance, as one can always declare all zeros to be the estimated vector and the distortion then is upper bounded by O( 1 n ). Consider the case when X is extremely sparse, i.e. α ↓ 0 as 1 n . Then a right comparison is to evaluate the average distortion per number of non-zero elements, E 1 αn ||X −X|| 2 . Using this as the performance metric we have from equation 9, When α is small then the average number of projections required such that the per non-zero element distortion is bounded by a constant, scales as O(n log n). This is indeed consistent with our results, in that the Sensing Capacity goes down to zero as 1 log n .
X is sparse, i.e. α < 1 but not very small. From results on achievable sensing capacity we have that In order to compare the results we fix, performance guarantee of P r(d(X,X) ≥ d 0 ) ≤ ǫ for a given Sensing Capacity and from bounds obtained in [9]. Our bounds are sharper.
For the special case of binary alphabet we have the following scaling orders for the number of projections in both cases, from achievable sensing capacity we have m 1 ≥ O(nH 2 (α)) and from results in [9] we have m 2 ≥ O(αn log n). A plot of these orders as a function of α for a fixed n is shown in figure, 4.

VIII. EFFECT OF STRUCTURE OF G
In this section we will show that effect of structure of G on sensing capacity. This section is divided into several subsections and the discussion is self-contained. In section VIII-A we will show that for the Gaussian ensemble, the sensing capacity reduces for when diversity is low. Following that in section VIII-B we will show the effect of correlation across columns in the sensing matrix for the Gaussian ensemble on achievable sensing capacity. In section VIII-C we will present a general result for a generic sensing matrix G which will subsequently be used to highlight the effect of structures such as that induced via random filtering using a FIR filter with/without downsampling as considered in [20].

A. Effect of sensing diversity, Gaussian ensemble
In order to show the effect of sensing diversity we evaluate the mutual information E G I(X; Y|G) using the intuition described in the introduction. To this end we have the following lemma.
where the expectation is evaluated over the distribution Proof: See Appendix.
In the above lemma j plays the role of number of overlaps between the projection vector and the sparse signal. As the diversity reduces this overlap reduces and the mutual information decreases. We will illustrate this by considering the extreme case when β ↓ with n as 1 n . For this case we have, The effect is illustrated in figure 5. Thus low sensing diversity implies low sensing capacity.

B. Effect of correlation in G on achievable sensing capacity
In this section we will show that correlation in sensing matrix G reduces achievable capacity. Correlation in G can arise due to many physical reasons such as correlated scattering, correlation of gains across modalities in sensing which may arise due to the physical construction of the sensor. Naturally there can be direct relations between various phenomena that can lead to such correlation. This is captured by assuming that there is correlation across the columns of G. Consider the upper bound to the probability of error as derived in section IV, In the above expression, the term for each i are independent Gaussian random variables with zero mean and variance given by-∆ T Σ Gi ∆ where ∆ is the vector ∆ = X − X ′ and Σ Gi is the covariance matrix (symmetric and positive semi-definite) of the i-th row of G. By construction, we know that 1 n ∆ T ∆ ≥ 2d 0 and note that in the worst case, where λ min is the minimum eigenvalue of the normalized covariance matrixΣ Gi . Proceeding in a manner similar to that in the proof of lemma 6.2 we have that, From the above expression one can see that achievable sensing capacity falls in general, since λ min ≤ 1 as compared to the case when the elements of G are uncorrelated in which case λ min = 1 = λ max .

C. Deterministic G
In this section we will consider deterministic matrices G and provide upper bounds to sensing capacity for the general case. To this end denote the rows of G as G i , i = 1, 2, . . . , m. Let the cross-correlations of these rows be denoted as: As before to ensure the SNR, to be fixed we impose G T i G i = 1 for all i. Then we have the following result:

Lemma 8.2:
For the generative models for the signal X as outlined in the problem set-up, an upper bound for the sensing capacity for a deterministic sensing matrix G ∈ R m×n is given by: Proof: We will evaluate I(X; Y|G) via the straightforward method, where Y * is a Gaussian random vector obtained via GX * where X * is now a Gaussian random vector with i.i.d components and with the same covariance as X under the generative model(s). We will now upper bound the entropy of Y via, The result then follows by evaluating the MMSE error given by, Plugging in the quantities the result follows.
Let us see the implications of the above result for one particular type of sensing matrix architecture induced via a random filtering and downsampling, considered in [20]. The output of the filter of length L < n can be modeled via multiplication of X via a Toeplitz matrix (with a banded structure). The overlap between successive rows of the matrix G is L − 1 in this case implying a large cross correlation r i . From lemma 12 it follows that larger cross correlation in rows implies poor sensing capacity. Also note that for a filtering architecture one has to address a coverage issue wherein it is required that m > n − L + 1.
This implies that L > n − m + 1. Thus the filter length has to be sufficiently large which implies that cross-correlation is also large.
Indeed randomizing each row will lead to low cross-correlation (in an expected sense) but the coverage issue still needs to be addressed. On the other hand one can subsample the output signal of length n−L+1 by some factor so as to reduce the cross correlation yet ensuring coverage. In this case the matrix almost becomes like a upper triangular matrix and there is a significant loss of sensing diversity. A loose tradeoff between the filter-length L and the sampling factor d (say) immediately follows from lemma 12 where the cross correlation changes according to The main motivation for considering this ensemble comes from scenarios where randomization in the elements of G is not feasible, e.g. field estimation from smoothed data. In this case each sensor measures a superposition of the signals that are in the sensing range of the sensor. This leads us to consider other types of modalities, e.g. contiguous sampling of X by each sensor Vs random sampling for β < 1. An illustration of the two types of sampling is shown in figure 6. We reveal the following contrast for the two cases for same β < 1 Lemma 9.1: Random Sampling: For the {0, 1} ensemble for sensing matrices consider the case when each row of G has βn ones randomly placed in n positions. Then for discrete X ∈ {0, 1} n drawn Bernoulli(α) and for d 0 < α, where H(.) is the discrete entropy function and where J is a random variable with distribution given by where each row of G has βn consecutive ones randomly placed with wrap around. Then for discrete X ∈ {0, 1} n drawn Bernoulli(α) and d 0 < α, As seen the upper bound, C rand (d 0 ) ≥ C contg. (d 0 ). Thus randomization in G performs better. The difference is shown in figure 7 for a low sparsity scenario. The proofs of the lemmas 9.1 and 9.2 follow from the upper bounds to the mutual information terms as provided in section XII and then applying the necessary conditions for the lower bound on the probability of error to be lower bounded by zero.

X. ESTIMATION OF FUNCTIONS OF X
The analysis of lower bounds to the probability of error presented in this paper extend in a straightforward way to estimation of functions of X. In this section we will consider one such scenario that has received attention in relation to problems arising in physics. The discussion below will reveal the power of the method presented in this work and it is easily capable of handling more complicated cases and scenarios, though the computation of the terms involved in the analysis may become hard. Note that due to loose overbounding of mutual information (we basically got rid of noise) the upper bounds are greater than in the case of Gaussian ensemble.

A. Detecting the sign pattern of X
Of particular interest is to estimate the sign pattern of the underlying signal X. To this end define a new random variable U, via The corresponding n dimensional extension and probability distribution on U is induced directly via P X . In such a case note that U → X → Y →Û(Y) forms a Markov chain. To this end consider an error event defined via, Let X n = {X 1 , ..., X n } be an i.i.d. sequence where each variable X i is distributed according to a distribution P X defined on the alphabet X . Denote P X n (P X ) n the n-dimensional distribution induced by P X . Let the space X n be equipped with a distance measure d(., .) with the distance in n dimensions given by d n (X n , Z n ) = n k=1 d(X k , Z k ) for X n , Z n ∈ X n . Given ǫ > 0, there exist a set of points Z n 1 , ..., Z Nǫ(n,d0) ⊂ X n such that, where B i X n : 1 n d n (X n , Z n i ) ≤ d 0 , i.e., the d 0 balls around the set of points cover the space X n in probability exceeding 1 − ǫ.
Given such set of points there exists a function f (X n ) : X n → Z n i s.t. P r 1 n d n (X n , Z n i ) ≤ d 0 ≥ 1 − ǫ. To this end, let T PXn denote the set of δ -typical sequences in X n that are typical P X n , i.e.
whereP (X n ) is the empirical distribution induced by the sequence X n . We have the following lemma from [21].
Lemma 11.1: For any η > 0 there exists an n 0 such that for all n ≥ n 0 , such that In the following we choose η = δ. Given that there is an algorithmX n (Y) that produces an estimate of X n given the observation Y. To this end define an error event on the algorithm as follows, Define another event A n as follows Note that since X n is drawn according to P X n and given δ > 0 we choose n 0 such that conditions of lemma 11.1 are satisfied. In the following we choose n ≥ n 0 (δ). Then a priori, P r(A n = 1) ≥ (1 − δ). Now, consider the following expansion, This implies that Now the term P n e H(f (X n )|Y, E n = 1, A n ) ≤ P n e log N ǫ (n, d 0 ). Note that the second term does not go to zero. For the second term we have that, The first term on R.H.S in the above inequality is bounded via, where S is the set given by, is the set distance between two sets. Now note that where the second inequality follows from data processing inequality over the Markov chain f (X n ) ↔ X n ↔ Y. Thus we have, The above inequality is true for all the mappings f satisfying the distortion criteria for mapping X n and for all choices of the set satisfying the covering condition given by 11.2. We now state the following lemma for a minimal covering, taken from [16]. Lemma 11.2: Given ǫ > 0 and the distortion measure d n (., .), let N ǫ (n, d 0 ) be the minimal number of points Z n 1 , ..., Z n Nǫ(n,d0) ⊂ X n satisfying the covering condition, Let N ǫ (n, d 0 ) be the minimal such number. Then, where R X (ǫ, d 0 ) is the infimum of the ǫachievable rates at distortion level d 0 .
Note that lim ǫ↓0 R X (ǫ, d 0 ) = R X (d 0 ) where R X (d 0 ) = min p(X|X) I(X; X) subject to 1 n E(d(X n ,X n )) ≤ d 0 . In order to lower bound P n e we choose the mapping f (X n ) to correspond to the minimal cover. Also w.l.o.g we choose δ = ǫ. We note the following. 1) From lemma 11.1, given ǫ > 0, ∃n 0 (ǫ) such that for all n ≥ n 0 (ǫ), we have P r(T PXn ) ≥ 1 − ǫ.
3) From the definition of the rate distortion function we have for the choice of the functions f (X n ) that satisfies the distortion criteria, I(f (X n ); X n ) ≥ nR X (ǫ, d 0 ).
Therefore we have for n ≥ max(n 0 , n 1 ), Clearly, log |S| ≤ n 2 R X (ǫ, d 0 ). d) Limiting case: Since the choice of ǫ, β is arbitrary we can choose them to be arbitrary small.
In fact we can choose ǫ, β ↓ 0. Also note that for every ǫ > 0 and β > 0 there exists n 2 (β) such that Therefore for all n ≥ max(n 0 , n 1 , n 2 ) in the limiting case when ǫ, β ↓ 0, we have This implies that The proof then follows by identifying K(n, d 0 ) = 1 n log |S|, and is bounded above by a constant.

B. Proof of lemma 3.2
Proof: Given an observation Y about the event X n . Define an error event, Expanding H(X n , E|Y) in two different ways we get that, Then we have for the lower bound on the probability of error that, see e.g., [16]. Thus for those values of distortion we have for all n,

C. Rate distortion function for the mixture Gaussian source under squared distortion measure
It has been shown in [22] that the rate distortion function for a mixture of two Gaussian sources with variances given by σ 1 with mixture ratio α and σ 0 with mixture ratio 1 − α, is given by For a strict sparsity model we have σ 2 0 → 0 we have that,

D. Bounds on Mutual information
In this section we will evaluate bounds on mutual information that will be useful in characterization of the Sensing Capacity. Given that the matrix G is chosen independently of X we expand the mutual information between X and Y, G in two different ways as follows - To this end we have the following lemma. Note also that conditioned on X and Y the G has a Gaussian distribution. Now note that, h(G|Y, X).
First note that, rows of G are independent of each other given X and Y. So we can write, h(G|Y, X) = mh(g 1 |Y, X) where g 1 is the first row of the matrix G. Since g is Gaussian one can find the residual entropy in terms of the residual MMSE error in estimation of g given X and Y. This error is given by - The second equation follows from the fact that G is independent of X and given X the row g 1 is independent of other observations, Y 2 , ..., Y m . First note that given X we also know which positions of X are zeros. So without lossof generality we can assume that the first k elements of X are non-zeros and the rest are zeros. Now note the following, where 0 n−k is a column vector of n − k zeros.
Therefore we have, h(g 1 |Y 1 , X) = 1 2 log(2πe) k det P n I k − P n X 1:k Σ −1 Y1|X P n X T 1:k + n−k 2 log 2πe P n Note that the second term on the R.H.S in the above equation corresponds to the entropy of those elements of the row g 1 that have no correlation with Y, i.e. nothing can be inferred about these elements since they overlap with zero elements of X. Now, using the equation det(I + AB) = det(I + BA), we have that h(g 1 |Y 1 , X) = 1 2 log( 2πeP n ) k det 1 − X T 1:k Σ −1 Y1|X P n X 1:k = 1 2 log ( 2πeP Plugging in all the expressions we get a lower bound on the mutual information I(X; Y|G) - In contrast to the upper bound derived in the proof of lemmas 5.1 and 5.2, this alternate derivation provides a handle to understand the effect of the structure of G on the mutual information when one is not allowed to pick a maximizing input distribution on X. Moreover the above derivation can potentially handle scenarios of correlated G. Below we will use the above result in order to prove lemma 8.1.

E. Proof of lemma 8.1
To this end let l = βn and is fixed, i.e. there are only l non-zero terms in each row of matrix G. We have h(G) = ml 2 log 2πe P l + mh 2 (β) Now we will first evaluate h(G|Y, X). Proceeding as in derivation of lemma 11.3, we have that, h(G|X, Y) = mh(g 1 |Y 1 , X) + mh 2 (β) where one can see that if the matrix G is chosen from a Gaussian ensemble then given X and Y it tells nothing about the positions of the non-zeros in each row. Hence the additive term h 2 (β) appears in both terms and is thus canceled in the overall calculations. So we will omit this term in the subsequent calculations. To this end, let j denote the number of overlaps of the vector g 1 and the k-sparse vector X.
Given Y 1 and X one can only infer something about those elements of G that contribute to Y 1 . Given the number of overlaps j we then have h(g 1 |X, Y 1 , j) = l−j 2 log 2πe P l + 1 2 log ( 2πeP where we have assumed without loss of generality that the first j elements of X are non-zero and overlap with elements of the first row. Now note that, In this section we will derive upper bounds to the mutual information I(X; Y|G) for the case when the matrix is chosen from a {0, 1} ensemble. First it is easily seen that for this ensemble a full diversity leads to loss of rank and thus the mutual information is close to zero. So we will only consider the case β < 1. Given that X is k-sparse we have,