Lower Bounds for Sparse Recovery

Details Lower Bounds for Sparse Recovery Lower Bounds for Sparse Recovery

2011-06-02

arxiv.org/abs/1106.0365v2

Computer Science

Data Structures and Algorithms

11 pages. Appeared at SODA 2010

Scientific paper

We consider the following k-sparse recovery problem: design an m x n matrix A, such that for any signal x, given Ax we can efficiently recover x' satisfying ||x-x'||_1 <= C min_{k-sparse} x"} ||x-x"||_1. It is known that there exist matrices A with this property that have only O(k log (n/k)) rows. In this paper we show that this bound is tight. Our bound holds even for the more general /randomized/ version of the problem, where A is a random variable and the recovery algorithm is required to work for any fixed x with constant probability (over A).

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-494901