Abstract:
In this proposal, we look at a number of problems under the large umbrella of Statistical Reconstruction motivated by applications in crowd-sourcing, compressed sensing, advertisements and recommendation systems. At a high level, the aim in most such problems is to recover a latent combinatorial property of a set of elements from a minimum number of distorted or restricted observations. In the process, we demonstrate the use of diverse statistical, analytic and combinatorial techniques that are interesting in their own right.
The first group of problems aims at recovering latent clusters described on a set of elements by making simple queries to an oracle. We show different querying schemes and prove both necessary and sufficient query complexity results for a variety of settings namely: 1) The latent clusters can be hard, overlapping or even fuzzy 2) Queries can be noiseless, noisy or quantized 3) The recovery guarantee can be exact or approximate. In the second part, we look at a class of problems where we have several unknown objects and for each query, it is hidden which object the query response corresponds to. Under this umbrella, we prove novel results for Trace Reconstruction, Parameter Recovery in Mixture Models, Mixture of Sparse Linear Regression and Mixture of Sparse Linear Classifiers improving state of the art results in a number of cases while proving the first guarantees for others. In the third part, we propose and study a novel random graph model of communities that we call the Geometric Block Model (GBM) in order to capture the inherent geometric features of many community detection (clustering) problems. Finally, we also propose several new directions for future works and improvements.
Advisor: Arya Mazumdar