Sensing aware dimensionality reduction for nearest neighbor classification of high dimensional signals

A successful approach to high-dimensional classification problems has been to couple nearest-neighbor classification with distance-preserving data dimensionality reduction via independent random projections. In many problems, however, the observed data is related to a natural set of latent variables through a non-trivial sensing process. A common approach in such cases is to either ignore the sensing process or to invert it and then proceed with dimensionality reduction and classifier design. Inversion can be costly and may be unnecessary if the end goal is classification. Rather than either ignoring sensing structure or using it for explicit inversion, we propose using “structured random projections” whose correlation explicitly accounts for the sensing structure. We show examples comparing the performance of independent random projections of observed data, independent random projections of reconstructed data, and our new structured random projections of observed data which demonstrate the benefits of our approach.