On the Fundamental Limits of Adaptive Sensing

By Ery Arias-Castro, E.J. Candes, Mark A. Davenport. 2011

141 citations recorded by the source corpus.

Suppose we can sequentially acquire arbitrary linear measurements of an n -dimensional vector x resulting in the linear model y = A x + z, where z represents measurement noise. If the signal is known to be sparse, one would expect the following folk theorem to be true: choosing an adaptive strategy which cleverly selects the next row of A based on what has been previously observed should do far better than a nonadaptive strategy which sets the rows of A ahead of time, thus not trying to learn anything about the signal in between observations. This paper shows that the folk theorem is false. We prove that the advantages offered by clever adaptive strategies and sophisticated estimation procedures-no matter how intractable-over classical compressed acquisition/recovery schemes are, in general, minimal.

Subfields: Computational Mechanics, Computer Networks and Communications, Statistics and Probability, Information Theory, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Networks and Communications

In Statistics and Probability

In Information Theory

In Signal Processing

Citations in the corpus

Minimax Optimal Procedures for Locally Private Estimation (2016, methodology): “Under the conditions of the previous paragraph, we have We provide a proof of Lemma 1 in Section I.1 (see also the article Arias-Castro, Candés, and Davenport 2013).”
Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates (2013, methodology): “By letting P+j denote the joint distribution over the random index V and Z conditional on the jth coordinate Vj = 1 (and similarly for P−j), we obtain the following sharper version of Assouad’s lemma [4] (see also the papers [3, 19]; we provide a proof in Appendix F.”
Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations (2013, methodology): “Before embarking on our proofs, we assume all optimization algorithms are deterministic (see [35]).”
Minimax rates for memory-bounded sparse linear regression (2015, methodology): “We prove the theorem using an extension of Assouad’s method, which transforms the minimax lower bounding problem into one of multiple hypothesis tests (Assouad, 1983; Arias-Castro et al., 2013; Shamir, 2014).”
Finding and Leveraging Structure in Learning Problems (2012, background): “[9] Davenport and Arias-Castro [56] Malloy and Nowak [136]”
On the Randomized Complexity of Minimizing a Convex Quadratic Function (2018, methodology): “Due to the noiseless oracle model, our setting is most similar to that of Price and Woodruﬀ [Price and Woodruﬀ, 2013], whereas other works [Arias-Castro et al., 2013, Castro and T´anczos, 2017, Castro et al., 2014] study measurements contaminated with noise.”
A ug 2 01 4 Local Privacy , Data Processing Inequalities , and Minimax Rates (2018, methodology): “Letting P±j denote the joint distribution over the random index V and Z conditional on the jth coordinate Vj = ±1, we are able to establish the following sharpening of Assouad’s lemma [5, 4] (see Appendix F.”
Optimality guarantees for distributed statistical estimation (2014, methodology): “ar, our random vectors V must have independent coordinates, and we similarly require the vectors X to have independent coordinates. In standard “packing” constructions for lower bounds, however (e.g. [35, 31, 2, 9]), it seems diﬃcult to construct vectors with independent coordinates, for example, in”
Memory, Communication, and Statistical Queries (2016, methodology): “Theorem 11 is based on Assouad’s method (Assouad, 1983), a lower bound technique from the information theory literature which has recently found success in analyzing adaptive communication algorithms (Arias-Castro et al., 2013; Duchi et al., 2013; Steinhardt and Duchi, 2015).”