An Estimation Theoretic Approach for Sparsity Pattern Recovery in the Noisy Setting

Details An Estimation Theoretic Approach for Sparsity Pattern Recovery in the Noisy Setting An Estimation Theoretic Approach for Sparsity Pattern Recovery in the Noisy Setting

2009-11-25

arxiv.org/abs/0911.4880v1

Computer Science

Information Theory

Scientific paper

Compressed sensing deals with the reconstruction of sparse signals using a small number of linear measurements. One of the main challenges in compressed sensing is to find the support of a sparse signal. In the literature, several bounds on the scaling law of the number of measurements for successful support recovery have been derived where the main focus is on random Gaussian measurement matrices. In this paper, we investigate the noisy support recovery problem from an estimation theoretic point of view, where no specific assumption is made on the underlying measurement matrix. The linear measurements are perturbed by additive white Gaussian noise. We define the output of a support estimator to be a set of position values in increasing order. We set the error between the true and estimated supports as the $\ell_2$-norm of their difference. On the one hand, this choice allows us to use the machinery behind the $\ell_2$-norm error metric and on the other hand, converts the support recovery into a more intuitive and geometrical problem. First, by using the Hammersley-Chapman-Robbins (HCR) bound, we derive a fundamental lower bound on the performance of any \emph{unbiased} estimator of the support set. This lower bound provides us with necessary conditions on the number of measurements for reliable $\ell_2$-norm support recovery, which we specifically evaluate for uniform Gaussian measurement matrices. Then, we analyze the maximum likelihood estimator and derive conditions under which the HCR bound is achievable. This leads us to the number of measurements for the optimum decoder which is sufficient for reliable $\ell_2$-norm support recovery. Using this framework, we specifically evaluate sufficient conditions for uniform Gaussian measurement matrices.

Affiliated with

Also associated with

No associations

Rating

An Estimation Theoretic Approach for Sparsity Pattern Recovery in the Noisy Setting 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 An Estimation Theoretic Approach for Sparsity Pattern Recovery in the Noisy Setting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Estimation Theoretic Approach for Sparsity Pattern Recovery in the Noisy Setting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-624027