Estimating Unknown Sparsity in Compressed Sensing

Details Estimating Unknown Sparsity in Compressed Sensing Estimating Unknown Sparsity in Compressed Sensing

2012-04-19

arxiv.org/abs/1204.4227v1

Computer Science

Information Theory

16 pages

Scientific paper

Within the framework of compressed sensing, many theoretical guarantees for signal reconstruction require that the number of linear measurements $n$ exceed the sparsity ||x||_0 of the unknown signal x\in\R^p. However, if the sparsity ||x||_0 is unknown, the choice of $n$ remains problematic. This paper considers the problem of estimating the unknown degree of sparsity of $x$ with only a small number of linear measurements. Although we show that estimation of ||x||_0 is generally intractable in this framework, we consider an alternative measure of sparsity s(x):=\frac{\|x\|_1^2}{\|x\|_2^2}, which is a sharp lower bound on ||x||_0, and is more amenable to estimation. When $x$ is a non-negative vector, we propose a computationally efficient estimator \hat{s}(x), and use non-asymptotic methods to bound the relative error of \hat{s}(x) in terms of a finite number of measurements. Remarkably, the quality of estimation is \emph{dimension-free}, which ensures that \hat{s}(x) is well-suited to the high-dimensional regime where n<

Affiliated with

Also associated with

No associations

Rating

Estimating Unknown Sparsity in Compressed Sensing 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 Estimating Unknown Sparsity in Compressed Sensing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Estimating Unknown Sparsity in Compressed Sensing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-33762