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.
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.
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