On the Limits of Sequential Testing in High Dimensions

Details On the Limits of Sequential Testing in High Dimensions On the Limits of Sequential Testing in High Dimensions

2011-05-23

arxiv.org/abs/1105.4540v3

Computer Science

Information Theory

Asilomar 2011

Scientific paper

This paper presents results pertaining to sequential methods for support recovery of sparse signals in noise. Specifically, we show that any sequential measurement procedure fails provided the average number of measurements per dimension grows slower then log s / D(f0||f1) where s is the level of sparsity, and D(f0||f1) the Kullback-Leibler divergence between the underlying distributions. For comparison, we show any non-sequential procedure fails provided the number of measurements grows at a rate less than log n / D(f1||f0), where n is the total dimension of the problem. Lastly, we show that a simple procedure termed sequential thresholding guarantees exact support recovery provided the average number of measurements per dimension grows faster than (log s + log log n) / D(f0||f1), a mere additive factor more than the lower bound.

Affiliated with

Also associated with

No associations

Rating

On the Limits of Sequential Testing in High Dimensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Limits of Sequential Testing in High Dimensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Limits of Sequential Testing in High Dimensions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-22819