On the Power of Adaptivity in Sparse Recovery

DOI10.1109/FOCS.2011.83MaRDI QIDQ5495018zbMATH OpenOpenAlexFDO

Authors Eric Price, David P. Woodruff, Piotr Indyk

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.3850

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sampling theory in information and communication theory (94A20)

Abstract: The goal of (stable) sparse recovery is to recover a $k$-sparse approximation $x\ast$ of a vector $x$ from linear measurements of $x$. Specifically, the goal is to recover $x\ast$ 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(klog(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)kloglog(neps/k))$ measurements that uses $O(log\ast kloglog(neps/k))$ rounds. This is a significant improvement over the best possible non-adaptive bound. - A scheme with $m=O((1/eps)klog(k/eps)+klog(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,\mathrm{...},n-1$ using $O(logn)$ bits of space and $O(loglogn)$ passes, improving over the best possible space complexity achievable using a single pass.

Cited in

(15)

• An adaptivity hierarchy theorem for property testing
• Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy
• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• Improved algorithms for adaptive compressed sensing
• On low-risk heavy hitters and sparse recovery schemes
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Querying a Matrix Through Matrix-Vector Products.
• scientific article; zbMATH DE number 7053292 (Why is no real title available?)
• Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity
• Randomized approximation of summable sequences -- adaptive and non-adaptive
• Deterministic sparse Fourier transform with an _ guarantee
• Uniform approximation of vectors using adaptive randomized information
• A combinatorial approach to robust PCA
• Non-adaptive edge counting and sampling via bipartite independent set queries
• Adaptive and non-adaptive randomized approximation of high-dimensional vectors

This page was built for publication: On the Power of Adaptivity in Sparse Recovery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495018)