Georgia Institute of Technology College of Sciences

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.