(1+eps)-approximate Sparse Recovery

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

21 pages; appeared at FOCS 2011

Scientific paper

The problem central to sparse recovery and compressive sensing is that of stable sparse recovery: we want a distribution of matrices A in R^{m\times n} such that, for any x \in R^n and with probability at least 2/3 over A, there is an algorithm to recover x* from Ax with ||x* - x||_p <= C min_{k-sparse x'} ||x - x'||_p for some constant C > 1 and norm p. The measurement complexity of this problem is well understood for constant C > 1. However, in a variety of applications it is important to obtain C = 1 + eps for a small eps > 0, and this complexity is not well understood. We resolve the dependence on eps in the number of measurements required of a k-sparse recovery algorithm, up to polylogarithmic factors for the central cases of p = 1 and p = 2. Namely, we give new algorithms and lower bounds that show the number of measurements required is (1/eps^{p/2})k polylog(n). For p = 2, our bound of (1/eps) k log(n/k) is tight up to constant factors. We also give matching bounds when the output is required to be k-sparse, in which case we achieve (1/eps^p) k polylog(n). This shows the distinction between the complexity of sparse and non-sparse outputs is fundamental.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

(1+eps)-approximate Sparse 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 (1+eps)-approximate Sparse Recovery, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and (1+eps)-approximate Sparse Recovery will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-550699

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.