Compressive classification and the rare eclipse problem

Afonso S. Bandeira, Dustin G. Mixon, Benjamin Recht

This paper addresses the fundamental question of when convex sets remain disjoint after random projection. We provide an analysis using ideas from high-dimensional convex geometry.…