Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery

Details Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery

2009-10-02

arxiv.org/abs/0910.0456v3

Computer Science

Information Theory

submitted to IEEE Trans. on Information Theory

Scientific paper

Consider the $n$-dimensional vector $y=X\be+\e$, where $\be \in \R^p$ has only $k$ nonzero entries and $\e \in \R^n$ is a Gaussian noise. This can be viewed as a linear system with sparsity constraints, corrupted by noise. We find a non-asymptotic upper bound on the probability that the optimal decoder for $\beta$ declares a wrong sparsity pattern, given any generic perturbation matrix $X$. In the case when $X$ is randomly drawn from a Gaussian ensemble, we obtain asymptotically sharp sufficient conditions for exact recovery, which agree with the known necessary conditions previously established.

Affiliated with

Also associated with

No associations

Rating

Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery 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 Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-26795