Discriminative Partition Sparsity Analysis

Effective dimensionality reduction has been an attractive research area for many large-scale vision and multimedia tasks. Several recent methods attempt to learn optimized graph-based embedding for fast and accurate applications. In this paper, we propose a novel linear unsupervised algorithm, termed Discriminative Partition Sparsity Analysis (DPSA), explicitly considering different probabilistic distributions that exist over the data points, meanwhile preserving the natural locality relationship among the data. Specifically, the Gaussian mixture model (GMM) is first applied to partition all samples into several clusters. In each cluster, a number of sparse sub-graphs are computed via the ℓ1-norm constraint to optimally represent the intrinsic data structure. Such sub-graphs are demonstrated to be robust to data noise, automatically sparse and adaptive to the neighborhood. All the sub-graphs from the clusters are then combined into a whole discriminative optimization framework for final reduction. We have systematically evaluated our method on three image datasets: USPS digital hand-writing, CMU PIE face and CIFAR-10 tiny image, showing its accurate and robust performance for image classification.