Compressive classification and the rare eclipse problem

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

Research output: Chapter in Book/Report/Conference proceedingChapter


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. For ellipsoids, we provide a bound in terms of the distance between these ellipsoids and simple functions of their polynomial coefficients. As an application, this theorem provides bounds for compressive classification of convex sets. Rather than assuming that the data to be classified is sparse, our results show that the data can be acquired via very few measurements yet will remain linearly separable. We demonstrate the feasibility of this approach in the context of hyperspectral imaging.

Original languageEnglish (US)
Title of host publicationApplied and Numerical Harmonic Analysis
PublisherSpringer International Publishing
Number of pages24
StatePublished - 2017

Publication series

NameApplied and Numerical Harmonic Analysis
ISSN (Print)2296-5009
ISSN (Electronic)2296-5017


  • Compressive classification
  • Gordon’s theorem

ASJC Scopus subject areas

  • Applied Mathematics


Dive into the research topics of 'Compressive classification and the rare eclipse problem'. Together they form a unique fingerprint.

Cite this