event
Thursday 22 Sep 2011: Dimension Adaptiveness of the Compressive FLD Classifier
Dr. Ata Kaban - School of Computer Science, University of Birmingham
Harrison 170 15:00-16:00
Dimensionality reduction by non-adaptive stable embeddings, such as random projections and compressed sensing have been gaining popularity for their computational advantages and theoretical guarantees. We study the use of such techniques for high dimensional learning problems. This talk will present an analysis of Fisher's Linear Discriminant (FLD) classifier when some high dimensional data is only available in a randomly projected compressive form. In particular, for (sub)gaussian classes, the generalisation error of compressive FLD is upper-bounded in terms of quantities in the original data space, and the compression dimensionality required for good generalisation grows only as the log of the number of classes. Furthermore, if the data density does not fill the ambient space, then we can show the error is independent of the ambient dimension and depends only on the effective dimension.
