SqueezeFit: Label-aware dimensionality reduction by semidefinite programming
This work addresses dimensionality reduction for labeled data, offering a theoretically analyzable method, but it appears incremental as it builds on large margin nearest neighbor classification with a new relaxation.
The paper tackles the problem of finding a low-dimensional subspace that preserves prescribed distances between differently labeled points for applications like compressive classification, and introduces a semidefinite relaxation that provably recovers a planted projection operator.
Given labeled points in a high-dimensional vector space, we seek a low-dimensional subspace such that projecting onto this subspace maintains some prescribed distance between points of differing labels. Intended applications include compressive classification. Taking inspiration from large margin nearest neighbor classification, this paper introduces a semidefinite relaxation of this problem. Unlike its predecessors, this relaxation is amenable to theoretical analysis, allowing us to provably recover a planted projection operator from the data.