Sparse Matrix-based Random Projection for Classification

Weizhi Lu, Weiyu Li, Kidiyo Kpalma, Joseph Ronsin

Abstract

As a typical dimensionality reduction technique, random projection can be simply implemented with linear projection, while maintaining the pairwise distances of high-dimensional data with high probability. Considering this technique is mainly exploited for the task of classification, this paper is developed to study the construction of random matrix from the viewpoint of feature selection, rather than of traditional distance preservation. This yields a somewhat surprising theoretical result, that is, the sparse random matrix with exactly one nonzero element per column, can present better feature selection performance than other more dense matrices, if the projection dimension is sufficiently large (namely, not much smaller than the number of feature elements); otherwise, it will perform comparably to others. For random projection, this theoretical result implies considerable improvement on both complexity and performance, which is widely confirmed with the classification experiments on both synthetic data and real data.

Introduction

High-dimensional data processing, common in fields like genomics and computer vision, often requires dimensionality reduction to remain computationally feasible. Random Projection (RP) has emerged as a powerful tool for this purpose, traditionally justified by the Johnson-Lindenstrauss (JL) Lemma. The JL Lemma guarantees that a random linear projection can preserve pairwise distances between points with high probability.

However, most applications of RP serve as a preprocessing step for classification. In this context, the objective shifts from preserving geometric distances to maintaining or enhancing the discriminative power of features. This paper argues that traditional "dense" random matrices (e.g., Gaussian matrices) may actually hinder classification by "diluting" discriminative features through excessive averaging. Instead, the authors propose a shift toward feature selection via ultra-sparse matrices.

The Sparsest Matrix (StM) Approach

The researchers propose a specific sparse matrix structure, termed the Sparsest Matrix (StM), characterized by:

  • Structure: Each column contains exactly one non-zero entry.
  • Values: This entry is randomly assigned a value of $+1$ or $-1$.
  • Scaling: The matrix is normalized by a factor of $1/\sqrt{k}$, where $k$ is the target projection dimension.

Unlike previous "Very Sparse" methods that still involve multiple non-zero entries per column, StM acts as a randomized feature selector. It maps individual features to new dimensions without mixing them, thereby preserving the unique signal of discriminative "needles" in the high-dimensional "haystack."

Theoretical Justification

The core theoretical contribution is the analysis of the expected inter-class difference, $E(f)$, in the projected space. The authors modeled how the number of non-zero elements per column ($s$) affects this metric. Their findings indicate that $s=1$ provides the maximum expected difference between classes, suggesting that any increase in density ($s > 1$) actually reduces the discriminative signal.

Figure 1(a): Normalized expected inter-class difference E(f) as a function of sparsity s. The peak at s=1 demonstrates that the sparsest matrix maximizes class separation.

As shown in the figure above, the normalized expected difference is highest when $s=1$. While the values oscillate as $s$ increases, they never return to the peak achieved by the ultra-sparse configuration. This "Aha" moment confirms that for classification, less is indeed more.

Experimental Results

The StM approach was rigorously tested against Gaussian Matrices (GM), Sparse Matrices (SM), and Very Sparse Matrices (VSM) across various domains:

  • Face Recognition: On the FERET dataset, StM achieved an accuracy of 97.47% ($k=600$), vastly outperforming the Gaussian matrix's 86.57%.
  • Bioinformatics: In DNA microarray datasets (Colon, ALML, Lung), StM consistently matched or exceeded the performance of denser alternatives once the projection dimension $k$ reached a reasonable threshold (typically $>10\%$ of the original dimension $d$).
  • Text Classification: Large-scale tests on TDT2 and RCV1 confirmed that StM maintains its advantage even in extremely high-dimensional, sparse text data.

Conclusion

This research demonstrates that for classification tasks, random projection should be viewed through the lens of feature selection rather than distance preservation. By using a matrix with exactly one non-zero element per column, practitioners can achieve higher classification accuracy while significantly reducing computational complexity. The StM method proves that when the projection dimension is sufficiently large, ultra-sparsity is not just a computational convenience, but a theoretical optimum for preserving discriminative information.

Summary updated

Abstract

As a typical dimensionality reduction technique, random projection can be simply implemented with linear projection, while maintaining the pairwise distances of high-dimensional data with high probability. Considering this technique is mainly exploited for the task of classification, this paper is developed to study the construction of random matrix from the viewpoint of feature selection, rather than of traditional distance preservation. This yields a somewhat surprising theoretical result, that is, the sparse random matrix with exactly one nonzero element per column, can present better feature selection performance than other more dense matrices, if the projection dimension is sufficiently large (namely, not much smaller than the number of feature elements); otherwise, it will perform comparably to others. For random projection, this theoretical result implies considerable improvement on both complexity and performance, which is widely confirmed with the classification experiments on both synthetic data and real data.
BibTeX
@misc{lu2013sparse,
  author = {Weizhi Lu and Weiyu Li and Kidiyo Kpalma and Joseph Ronsin},
  title = {{Sparse Matrix-based Random Projection for Classification}},
  year = {2013},
  eprint = {1312.3522},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1312.3522},
}
Figure