Data Science Part 23: Performance Limits

To design "the best" sparse recovery system, it often helps to know what we're looking at. Is it a deterministic signal? Then we must account for all possible signals within class. Is it a random signal? Then we utilize a probabilistic class where some are more likely than others. Is it a strictly sparse signal? Then most entries are zero. Is it a compressible signal? Then sorted entries have some rate of decay. There can also be structured and simple signals as well. 

We also need to know the quality of reconstruction. Do we always get perfect reconstruction? Do we have support set recovery? Do we use squared error? Do we use estimated value error? Worst case error? There are many possible cases. What was the complexity class of the reconstruction algorithms. Was it polynomial? Linear or better? How would we account for imprecisions? Noise in measurements? With an uncalibrated matrix? 

Our fundamental goal is to minimize measurements and compressed sensing tries to reduce resource consumption due to measurements and as a result the analog to digital rate and power required for the operation. As Donoho says, “Why go to so much effort to acquire all the data when most of what we get will be thrown away?" 

The measurement process is analog, and we can assume Gaussian noise for the ease of analysis and generalize to Non-Gaussian noise. For a measurement model, we can have a signal entry as Xn = BnUn with a Bernoulli probability distribution Bernoulli(ε), which is sparse, where UN ~ PU. 

For a non-sparse input we can have ε = 1 and as a result Xn = Un. The next thing we can do is to go over the noise and matrix model. With noisy measurements we can define the solution as 

y = (γ)^(1/2) y0 + z. γ will be indicated as the signal to noise ratio. 

The early result is to model the process y0 -> y as a measurement channel and then decode at the end. The measurements provide information, and the preliminary single-letter is bound for compressed sensing and linear measurement systems. 

These traits can be utilized in bandpass multiuser detection, single-letter bounds, bandpass algorithms for compressed sensing, and other arbitrary noise. An example of an experiment I can digress here is Precise Single Letter Characterization of Optimal Recovery. 

A single letter expression describes limiting the best possible performance in a system in the limit of large block lengths. The capacity channel C is the largest number of bits that can be communicated reliably over a mposy channel. R(D) is the rate of bits used to describe an input source up to size D. Signle letter performance characterizes the best possible performance, which is a limit (not available) but we can set up converse bounds for his.  

The matrix vector product y = (γ)^(1/2)Φx can be interpreted as an input X going through source encoder, followed by the channel encoder and then adding noise z to y0 (y = y0 + z). Say there are N measurements and capacity C which means we cannot have more than M/C reliable bits of information with input of lenght R. If we encode at rate R(D) then then the number of bits on an open source encoder is N(R(D)) so we get NR(D) <= M/C. The measurement rate is subsequently δ = M/N. >= R(D) / C. The bound allows for Gaussian, Poisson and many other types of channels.  

Remember Φ ∈ RMxN has unit norm columns on average. 

Ultimately, given Xn which is a complicated n-dimensional vector, we want a simple characterization of its quantity. The large system limit is 

. How do we estimate Xn? We can say that Xn is statistically identical to the scalar measurement with the signal to noise ratio SNR. Realistically we need to estimate Xn from the noisier scalar measurement. The estimation quality from (Y,Φ) is just as good as the noisier scalar observation and is statistically equivalent to 

which is a list of Gaussian random variables. and therefor appriximate yn as 

which is a scalar channel estimation problem. We want to modulate the input then having the square root, and then add noise. 

The variance is defined as

and we can conclude that

, and we can  conclude that the minimum squared error is

.

. The take home point is we utilize a degraded scalar channel, and this is used in CDMA detection, etc. ƞ is the degradation of the model and we can estimate it as follows: 

Where mmse is the Minimum mean square error.