text: 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.
  @cite_15: 
  @cite_7: Recent theoretical work has identified random projection as a promising dimensionality reduction technique for learning mixtures of Gaussians. Here we summarize these results and illustrate them by a wide variety of experiments on synthetic and real data.
  @cite_12: Mixtures of Gaussians are among the most fundamental and widely used statistical models. Current techniques for learning such mixtures from data are local search heuristics with weak performance guarantees. We present the first provably correct algorithm for learning a mixture of Gaussians. This algorithm is very simple and returns the true centers of the Gaussians to within the precision specified by the user with high probability. It runs in time only linear in the dimension of the data and polynomial in the number of Gaussians.
summary: It is striking that, to date, all of the work in compressive classification has focused on classes of low dimension. This is perhaps an artifact of the mindset of compressed sensing, in which the projection preserves all information on coordinate planes of sufficiently small dimension. However, classification should not require nearly as much information as signal reconstruction does, and so we expect to be able to compressively classify into classes of full dimension; indeed, we allow two points in a common class to be mapped to the same compressive measurement, as this will not affect the classification. A Boolean version of this idea is studied in @cite_15 , which considers both random and optimality constructed projections. In the continuous setting, the closest existing work is that of Dasgupta @cite_12 @cite_7 , which uses random projections to learn a mixture of Gaussians. In particular, Dasgupta shows that sufficiently separated Gaussians stay separated after random projection. In the next section, we prove a similar result about ellipsoids, but with a sharper notion of separation.