Randomized Subspace Learning Algorithms with Subspace Structure Preservation Guarantees

Devansh Arpit, Gaurav Srivastava, Venu Govindaraju

Introduction

In the domain of biometric security, the concept of "cancelable biometrics" is paramount. Unlike traditional passwords, physiological traits such as faces or fingerprints cannot be reset if compromised. Cancelable biometrics address this by applying repeatable, intentional distortions to biometric data before storage. If a template is stolen, the system parameters are updated to generate a new, distinct template.

Random Projection (RP) has emerged as a popular technique for this purpose due to its computational efficiency and inherent obfuscation. While the Johnson-Lindenstrauss lemma provides a foundation for RP in general dimensionality reduction, its specific efficacy in preserving the geometric structures necessary for classification—namely, linear subspaces—has lacked a rigorous theoretical explanation. This paper provides that foundation by analyzing how RP preserves the "Independent Subspace Structure" (ISS) of a dataset.

Theoretical Framework: Subspace Structure Preservation

The authors propose that biometric classes, such as a single individual's face under varying environmental conditions, naturally reside within distinct linear subspaces. To quantify the separability of these classes, they introduce the Subspace Margin, a measure of the geometric distance between subspaces.

A key contribution of this work is the Cosine Preservation Lemma, which demonstrates that the cosine of the angle between vectors is approximately maintained under random projection. Crucially, the authors prove that the required dimensionality ($m$) to preserve this structure grows only logarithmically with the number of samples ($N$), independent of the original high-dimensional space ($n$). This explains why high-resolution biometric data can be significantly compressed without losing the ability to distinguish between individuals.

Experimental Methodology

The theoretical findings were validated using two benchmark face recognition datasets:

  • Extended Yale Dataset B: Contains 2,414 images of 38 individuals under diverse lighting conditions.
  • CMU PIE Dataset: A large database of 68 people; the authors utilized a subset of the first 10 classes for evaluation.

The classification pipeline utilized Sparse Representation-based Classification (SRC), an algorithm specifically designed to exploit the underlying subspace structure of data.

Key Results

The empirical results strongly support the theoretical claims regarding speed, accuracy, and robustness.

Computational Efficiency

One of the most striking advantages of RP is its speed. Because the projection matrix is non-adaptive and does not require data-driven training (unlike PCA), the computational overhead is minimal. On the Extended Yale Dataset B, RP completed dimensionality reduction in just 1.59ms, whereas PCA required 322.04ms—representing a speedup of over 200x.

Computational time (ms) comparison between RP and PCA on the Extended Yale Dataset B.

Classification Accuracy and Robustness

Despite its simplicity, RP achieves classification performance comparable to or exceeding that of PCA. For instance, on the Yale B dataset, RP reached 97.93% accuracy at 500 dimensions, compared to 96.86% for PCA.

Furthermore, the authors' analysis of "rejection probability"—the likelihood that the subspace structure is compromised during projection—showed a sharp decline as the projected dimensionality $m$ increased, aligning perfectly with the derived mathematical bounds.

Rejection probability P vs. projected dimensionality m for different error tolerances epsilon.

Discussion and Future Work

While RP provides a robust foundation for cancelable biometrics, it is not a standalone security solution. If the projection matrix is compromised, an attacker could potentially approximate the original biometric trait. Therefore, RP should be integrated with additional layers such as secure hashing.

Future research directions include extending this analysis to non-linear manifolds, as the current work assumes linear subspace structures. Additionally, addressing the distortion of absolute inner products for vectors of varying lengths remains an open challenge.

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 Algorithms with Subspace Structure Preservation Guarantees}},
  year = {2014},
  eprint = {1401.4489},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.4489},
}
Figure