Randomized Subspace Learning with Structure Preservation

Devansh Arpit, Gaurav Srivastava, Venu Govindaraju

Abstract

Modeling high-dimensional data as a union of independent or disjoint subspaces is a powerful paradigm in computer vision and signal processing. However, the computational complexity of algorithms operating in these high-dimensional spaces often limits their practical application. While dimensionality reduction is a standard solution, traditional techniques risk destroying the underlying subspace structure. This paper formalizes the concept of Independent Subspace Structure and proposes two randomized algorithms—one supervised and one unsupervised—that theoretically preserve this structure. We demonstrate that in a supervised setting, $2K$ projection vectors are sufficient to preserve the structure of $K$-class data. In the unsupervised framework, we show that random projections can preserve this structure without requiring class labels. Our theoretical analysis is supported by empirical results on both synthetic and real-world datasets.

Introduction

In modern data science, high-dimensional datasets are increasingly common, yet they often possess a low-intrinsic dimensionality. A widely used model for such data is the "union of subspaces," where data points are assumed to lie on or near a collection of low-dimensional linear subspaces. For instance, images of a human face under varying lighting conditions typically reside within a specific low-dimensional subspace.

The challenge lies in reducing the dimensionality of this data to improve algorithmic efficiency without "squashing" these distinct subspaces together. If the dimensionality reduction process does not preserve the separation between subspaces, subsequent tasks like clustering or classification become impossible. This paper investigates the theoretical limits of structure-preserving dimensionality reduction.

Theoretical Framework

Unsupervised Structure Preservation

The authors analyze unsupervised dimensionality reduction through the lens of the Johnson-Lindenstrauss Lemma and the concept of "Subspace Margin." They prove that random projections effectively preserve the cosine of the angles between vectors. If two subspaces are well-separated in the original high-dimensional space, they are highly likely to remain separated after being projected into a lower-dimensional space. A key finding is that the required number of dimensions ($m$) scales logarithmically with the number of data points ($N$), providing a clear mathematical budget for maintaining data integrity.

The Supervised $2K$ Rule

The paper’s most significant theoretical contribution is the proof regarding supervised subspace learning. The authors demonstrate that for any two disjoint subspaces, there exists a specific 2D plane where both subspaces collapse into two distinct lines. By extending this logic to $K$ classes, they prove that only $2K$ projection vectors are necessary to perfectly preserve the separability of the data. This suggests that for classification purposes, the required dimensionality is independent of the original data dimension and depends only on the number of categories.

Proposed Methodology

To implement the supervised $2K$ rule, the authors propose Algorithm 1, a heuristic approach designed to find the optimal projection vectors. Since finding the exact "principal vector pairs" is computationally difficult, the algorithm utilizes an iterative quadratic programming framework. It seeks to identify the vectors that maximize the separation between one specific class and the remainder of the dataset, effectively building the projection matrix one pair at a time.

Experimental Results

Datasets

  1. Synthetic Data: The researchers used randomly generated independent subspaces in $\mathbb{R}^{1000}$ to validate the mathematical bounds of their structure preservation proofs.
  2. Extended Yale Face Dataset B: This dataset contains frontal face images of 38 individuals under various lighting conditions. It serves as a benchmark for subspace modeling, as face images under different lights are known to cluster near low-dimensional subspaces.

Performance Metrics

On the Extended Yale B dataset, the proposed supervised method demonstrated superior performance with significantly fewer dimensions:

  • Proposed Supervised Method: 95.57% accuracy using only 76 dimensions ($2 \times 38$ classes).
  • Random Projection: 93.95% accuracy (at 90 dimensions).
  • PCA: 93.62% accuracy (at 90 dimensions).
  • LDA: 86.81% accuracy (at 37 dimensions).

In unsupervised tests, the authors reduced 10,000-dimensional face data to 900 dimensions with only a 0.6% loss in segmentation accuracy, confirming that random projection is a robust tool for structure preservation.

Key Insights and Discussion

  • The "Two Lines" Phenomenon: The discovery that any two complex subspaces can be represented as two lines on a 2D plane simplifies the conceptual understanding of dimensionality reduction for classification.
  • Preservation of Obtuse Angles: The research clarifies that random projections preserve obtuse angles (angles $> 90^\circ$), though sensitivity increases for angles near $90^\circ$ where the cosine is close to zero.
  • Efficiency vs. Optimality: While Algorithm 1 is a heuristic and may not always find the absolute global optimum in extremely noisy environments, its empirical performance suggests it is highly effective for real-world subspace separation.

Conclusion and Future Work

This paper provides a rigorous foundation for randomized subspace learning. By proving that $2K$ dimensions are sufficient for supervised structure preservation, the authors offer a path toward more efficient high-dimensional data processing. Future research may focus on refining the optimization process in Algorithm 1 to reduce the computational cost of finding the projection matrix for datasets with a very large number of classes ($K$).

Summary updated

Abstract

Modeling data as being sampled from a union of independent or disjoint sub-spaces has been widely applied to a number of real world applications. Recently, high dimensional data has come into focus because of advancements in computa-tional power and storage capacity. However, a number of algorithms that assume the aforementioned data model have high time complexity which makes them slow. Dimensionality reduction is a commonly used technique to tackle this problem. In this paper, we first formalize the concept of Independent Subspace Structure and then we propose two randomized algorithms (supervised and unsupervised) for subspace learning that theoretically preserve this structure for any given dataset. Under supervised setting, we show that 2K projection vectors are sufficient for structure preservation ofK class data. On the other hand for unsupervised frame-work, we show that random projection preserves this structure without the knowl-edge of labels. We support our theoretical analysis with empirical results on both synthetic and real world data. 1
BibTeX
@misc{arpit2014randomized,
  author = {Devansh Arpit and Gaurav Srivastava and Venu Govindaraju},
  title = {{Randomized Subspace Learning with Structure Preservation}},
  year = {2014},
  eprint = {1401.4489},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.4489},
}
Figure