1-bit compressed sensing, sparse binary regression, and random hyperplane tessellations

Stochastics Seminar
Thursday, March 14, 2013 - 3:05pm
1 hour (actually 50 minutes)
Skyles 006
University of Michigan
1-bit compressed sensing combines the dimension reduction of compressed sensing with extreme quantization -- only the sign of each linear measurement is retained.  We discuss recent convex-programming approaches with strong theoretical guarantees.  We also discuss connections to related statistical models such as sparse logistic regression. Behind these problems lies a geometric question about random hyperplane tessellations.  Picture a subset K of the unit sphere, as in the continents on the planet earth.  Now slice the sphere in half with a hyperplane, and then slice it several times more, thus cutting the set K into a number of sections.  How many random hyperplanes are needed to ensure that all sections have small diameter?  How is the geodesic distance between two points in K related to the number of hyperplanes separating them?  We show that a single geometric parameter, the mean width of K, governs the answers to these questions.