Computer Science – Data Structures and Algorithms
Scientific paper
2011-10-17
Computer Science
Data Structures and Algorithms
18 pages; appearing at FOCS 2011
Scientific paper
The goal of (stable) sparse recovery is to recover a $k$-sparse approximation $x*$ of a vector $x$ from linear measurements of $x$. Specifically, the goal is to recover $x*$ such that ||x-x*||_p <= C min_{k-sparse x'} ||x-x'||_q for some constant $C$ and norm parameters $p$ and $q$. It is known that, for $p=q=1$ or $p=q=2$, this task can be accomplished using $m=O(k \log (n/k))$ non-adaptive measurements [CRT06] and that this bound is tight [DIPW10,FPRU10,PW11]. In this paper we show that if one is allowed to perform measurements that are adaptive, then the number of measurements can be considerably reduced. Specifically, for $C=1+eps$ and $p=q=2$ we show - A scheme with $m=O((1/eps)k log log (n eps/k))$ measurements that uses $O(log* k \log \log (n eps/k))$ rounds. This is a significant improvement over the best possible non-adaptive bound. - A scheme with $m=O((1/eps) k log (k/eps) + k \log (n/k))$ measurements that uses /two/ rounds. This improves over the best possible non-adaptive bound. To the best of our knowledge, these are the first results of this type. As an independent application, we show how to solve the problem of finding a duplicate in a data stream of $n$ items drawn from ${1, 2, ..., n-1}$ using $O(log n)$ bits of space and $O(log log n)$ passes, improving over the best possible space complexity achievable using a single pass.
Indyk Piotr
Price Eric
Woodruff David P.
No associations
LandOfFree
On the Power of Adaptivity in 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 On the Power of Adaptivity in Sparse Recovery, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Power of Adaptivity in Sparse Recovery will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-289536