Information-theoretic Limits on the Classification of Gaussian Mixtures: Classification on the Grassmann Manifold

Motivated by applications in high-dimensional signal processing, we derive fundamental limits on the performance of compressive linear classifiers. By analogy with Shannon theory, we define the classification capacity, which quantifies the maximum number of classes that can be discriminated with low probability of error, and the diversity-discrimination tradeoff, which quantifies the tradeoff between the number of classes and the probability of classification error. For classification of Gaussian mixture models, we identify a duality between classification and communications over non-coherent multiple-antenna channels. This duality allows us to characterize the classification capacity and diversity-discrimination tradeoff using existing results from multiple-antenna communication. We also identify the easiest possible classification problems, which correspond to low-dimensional subspaces drawn from an appropriate Grassmann manifold.