Support Recovery from Linear Measurements Tradeoffs in the Measurement Constrained Regime

Abstract

In this thesis, we study problems under the theme of discovering joint sparsity structure in a set of high-dimensional data samples from linear measurements. Our primary focus is on the regime where the number of samples available can potentially be large, but we are constrained to access very few measurements per sample. This setting can be used model high-dimensional estimation tasks in a distributed setting, where storing or communicating more measurements per sample can be expensive. We first study a basic problem in this setting -- that of support recovery from linear measurements. In this problem, a set of n samples in d-dimensional Euclidean space, each having a support of size k, is accessed through m linear measurements per sample. The goal is to recover the unknown support, given knowledge of the m-dimensional measurements and the corresponding measurement matrices. This problem, also sometimes referred to as variable selection or model selection, has been extensively studied in the signal processing and statistics literature, and finds applications in source localization, hyperspectral imaging, heavy hitters detection in networks, and feature selection in regression. It is known that if we have m=\Omega(k \log d) measurements per sample, then even a single sample is sufficient for support recovery. As such, when we have access to multiple samples, an interesting question is whether we can perform recovery with fewer than k measurements per sample. This measurement-constrained setting is relatively less explored in the literature, and the optimal sample-measurement tradeoff was unknown prior to our work. We provide a tight characterization of the sample complexity of this problem, which together with previous results in the literature gives a full understanding of the scaling laws of this problem for different values of the ratio k/m...