Georgia Institute of Technology College of Sciences

Compressed sensing illustrates the possibility of acquiring and reconstructing sparse signals via underdetermined (linear) systems. It is believed that iid Gaussian measurement vectors give near optimal results, with the necessary number of measurements on the order of $s \log(n/s)$ - $n$ is ambient dimension and $s$ is the sparsity threshold. The recovery algorithm used above relies on a certain quasi-isometry property of the measurement matrix. A surprising result is that the same order of measurements gives an analogous quasi-isometry in the extreme quantization of one-bit sensing. Bylik and Lacey deliver this result as a consequence of a certain stochastic process on the sphere. We will discuss an alternative method that relies heavily on the VC-dimension of a class of subsets on the sphere.