Zoom Link: https://umass-amherst.zoom.us/j/91293842157
Abstract: While data in the real world is very high-dimensional, it generally has some underlying structure; for instance if we think of an image as a set of pixels with associated color values, most possible settings of color values correspond to something more like random colored noise than what we typically think of as a picture. With an appropriate transformation of basis, we can often convert this underlying structure into data "sparsity," giving us an equivalent representation of the data where the magnitude of the data is large in only a few directions relative to the ambient dimension. This motivates a variety of theoretical questions around designing algorithms that can exploit this data sparsity to achieve better performance than what would be possible naively, and in this thesis we tackle several such questions.
We first examine the question of simply approximating the level of sparsity of a signal under several different measurement models, a natural first step if the sparsity is to be exploited by other algorithms. Second, we look at a particular sparse signal recovery problem called "nonadaptive probabilistic group testing," and investigate the question of exactly how sparse the signal needs to be before the methods used for recovering sparse signals outperform those used for non-sparse signals. Third, we prove novel upper bounds on the number of measurements needed to recover a sparse signal in the "universal one-bit compressed sensing" model of sparse signal recovery. Fourth, we give some approximations of an information-theoretic quantity called the "index coding rate" of sparse and other highly-structured networks. For each of the problems we consider, we also discuss some remaining open questions and conjectures, as well as possible directions towards their solutions.
Committee: Arya Mazumdar (chair), Andrew McGregor, Cameron Musco, Marco Duarte (outside member)