Faculty Recruiting Support CICS

Algorithms to Exploit Data Sparsity

14 Feb
Friday, 02/14/2020 1:00pm to 3:00pm
PhD Dissertation Proposal Defense
Speaker: Larkin Flodin


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 small number of directions relative to the ambient dimension. The ability to perform these transformations motivates a variety of theoretical questions around designing algorithms that inherently exploit this data sparsity to achieve much 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 prove novel upper bounds on the number of measurements needed to approximately recover a sparse signal in the "universal one-bit compressed sensing" model. Third, we give some approximations of an information theoretic quantity called the "index coding rate" of sparse and other highly-structured networks. We also cover several directions for future work, including generalizations of some sparse signal recovery problems and tightening the gaps between lower and upper bounds for universal one-bit compressed sensing.

Advisor: Arya Mazumdar